The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation

By Shantanav Chakraborty, András Gilyén, Stacey Jeffery. International Colloquium on Automata, Languages and Programming, 2018

363 citations recorded by the source corpus.

We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/de04b33a476984b1306d8c7a5ef34d52189382ac

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Variational Quantum Linear Solver (2019, background): “Further improvements to HHL have reduced the complexity to linear κ scaling [7, 8] and polylogarithmic scaling in 1 /ϵ [9, 10], as well as improved the sparsity requirements [11].”
Challenges and opportunities in quantum optimization (2023, neutral): “It is therefore natural to ask whether quantum linear-system solvers 99–101 , followed by quantum state tomography, can be used to speedup such a task.”
Variational quantum algorithms (2020, background): “The classical algorithmic complexity for this task scales polynomially in the dimension N , whereas the now-famous HHL quantum algorithm [4] has a complexity that scales logarithmically in N , with some scaling improvements having been proposed [113– 116].”
Hamiltonian Simulation by Qubitization (2016, neutral): “4After the original preprint release of this manuscript, standard-form encoding has been replaced in the community by ‘block-encoding’ [29], which is a more informative description.”