Quantum Algorithm for Linear Systems of Equations

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 Ax⃗=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⃗†Mx⃗ 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⃗†Mx⃗ in time scaling roughly as N√κ. Here, we exhibit a quantum algorithm for estimating x⃗†Mx⃗ whose runtime is a polynomial of log(N) and κ. Indeed, for small values of κ [i.e., polylog(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.W. M. Keck Foundation Center for Extreme Quantum Information Theor