Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision

By Andrew M. Childs, Robin Kothari, Rolando D. Somma. SIAM journal on computing (Print), 2015

764 citations recorded by the source corpus.

Harrow, Hassidim, and Lloyd [Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified $N \times N$ matrix $A$ and an $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x} = \vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time ${poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

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 Computational Theory and Mathematics

Citations in the corpus

Emergent Quantum State Designs from Individual Many-Body Wave Functions (2021, methodology): “The proof is given in Appendices E and F and relies on higher-order concentration of measure results [50] as well as a polynomial approximation technique used in quantum algorithms for solving linear systems [51].”
Variational Quantum Linear Solver (2019, methodology): “Our numerical results were obtained by employing the layered Hardware-Efficient Ansatz of Fig.”
Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics (2018, methodology): “The methodology we describe is a distilled version of the results of a series of works on quantum algorithms [6, 11, 16, 17, 30, 41].”
Variational quantum algorithms for nonlinear problems (2019, background): “[18] A.”
Hamiltonian Simulation by Qubitization (2016, background): “Problem BCCKS [6] d-sparse [7] Evolution by ρ QPE QLSP [9] Gibbs [10] Ĥ Hamiltonian Hamiltonian Density matrix Unitary Matrix Hamiltonian Û Selects Ûj Isometry T̂ SWAP Any Any Any Ĝ Ûj coefficients Identity Purified ρ Any Any Any Solution e−iĤt e−iĤt e−iρ̂t Decision Ĥ−1 e−βĤ”
Generalized Quantum Signal Processing (2023, methodology): “The cost of doing so within error ε is then Õ(d(2)κ(2) log(4)(N) log(1/ε))) where κ is the condition number of the circulant matrix C using the inversion method of [30].”
Quantum computing for finance: Overview and prospects (2018, methodology): “Wang builds upon this work by applying modern methods for matrix inversion [67], and generalize this algorithm to non-sparse training data matrices [68].”