Article,
Quantum Algorithm for Linear Systems of Equations
Physical Review Letters, 103 (15): 150502+ (October 2009)
DOI: 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 A and a vector b ⃗ , find a vector x ⃗ such that A x ⃗= b ⃗ . We consider the case where one does not need to know the solution x ⃗ itself, but rather an approximation of the expectation value of some operator associated with x ⃗ , e.g., x ⃗ †M x ⃗ for some matrix M . In this case, when A is sparse, N × N and has condition number κ , the fastest known classical algorithms can find x ⃗ and estimate x ⃗ †M x ⃗ in time scaling roughly as N âˆs κ . Here, we exhibit a quantum algorithm for estimating x ⃗ †M x ⃗ whose runtime is a polynomial of log â�!`( N ) and κ . Indeed, for small values of κ i.e., poly log â�!`( N ) , we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
