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^dagger M x for some matrix M. In this case, when A is sparse, N x N and has condition number kappa, the fastest known classical algorithms run in time O(N sqrt(kappa) log(1/epsilon)) while our quantum algorithm runs in time O(log(N) kappa^2 log(1/epsilon)), an exponential improvement in N.