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.