Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision

Harrow, Hassidim, and Lloyd Phys. Rev. Lett. , 103 (2009), 150502 showed that for a suitably specified N N matrix A and an N-dimensional vector b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax = b. If A is sparse and well-conditioned, their algorithm runs in time poly (N, 1/), where is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in (1/), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on is prohibitive.