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) over right arrow, find a vector (x) over right arrow such that A (x) over right arrow = (b) over right arrow. We consider the case where one does not need to know the solution (x) over right arrow itself, but rather an approximation of the expectation value of some operator associated with (x) over right arrow, e.g., (x) over right arrow (dagger) M (x) over right arrow for some matrix M. In this case, when A is sparse, N x N and has condition number kappa, the fastest known classical algorithms can find (x) over right arrow and estimate (x) over right arrow (dagger) M (x) over right arrow in time scaling roughly as N root kappa. Here, we exhibit a quantum algorithm for estimating (x) over right arrow (dagger) M (x) over right arrow whose runtime is a polynomial of log(N) and kappa. Indeed, for small values of kappa [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.