Quantum Algorithm for Linear Systems of Equations
Top Cited Papers
- 7 October 2009
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 103 (15), 150502
- https://doi.org/10.1103/physrevlett.103.150502
Abstract
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix and a vector , find a vector such that . We consider the case where one does not need to know the solution itself, but rather an approximation of the expectation value of some operator associated with , e.g., for some matrix . In this case, when is sparse, and has condition number , the fastest known classical algorithms can find and estimate in time scaling roughly as . Here, we exhibit a quantum algorithm for estimating whose runtime is a polynomial of and . Indeed, for small values of [i.e., ], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
Keywords
Other Versions
This publication has 11 references indexed in Scilit:
- The Mathematical Theory of Finite Element MethodsPublished by Springer Science and Business Media LLC ,2008
- Efficient Quantum Algorithms for Simulating Sparse HamiltoniansCommunications in Mathematical Physics, 2006
- Smoothed Analysis of the Condition Numbers and Growth Factors of MatricesSIAM Journal on Matrix Analysis and Applications, 2006
- Engineering functional quantum algorithmsPhysical Review A, 2003
- Quantum amplitude amplification and estimationContemporary Mathematics, 2002
- Quantum FingerprintingPhysical Review Letters, 2001
- Limit on the Speed of Quantum Computation in Determining ParityPhysical Review Letters, 1998
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Optimum phase-shift estimation and the quantum description of the phase differencePhysical Review A, 1996
- Universal Quantum SimulatorsScience, 1996