title: Quantum algorithm for linear systems of equations.
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 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) Mx(-->) 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(-->) and estimate x(-->)(dagger) Mx(-->) in time scaling roughly as N square root(kappa). Here, we exhibit a quantum algorithm for estimating x(-->)(dagger) Mx(-->) 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.
authors.affiliation: Department of Mathematics, University of Bristol, Bristol, BS8 1TW, United Kingdom.
authors.forename: Aram W
authors.initials: AW
authors.lastname: Harrow
authors.forename: Avinatan
authors.initials: A
authors.lastname: Hassidim
authors.forename: Seth
authors.initials: S
authors.lastname: Lloyd