QUANTUM ALGORITHM FOR SYSTEMS OF LINEAR EQUATIONS WITH EXPONENTIALLY IMPROVED DEPENDENCE ON PRECISION

Harrow, Hassidim, and Lloyd showed that for a suitably specified N N matri A and N-dimensional vector (b) over right arrow , there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations A<()over right arrow> = (b) over right arrow . If A is sparse and well-conditioned, their algorithm runs in time poly(logN,1/epsilon), where ? is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/epsilon), eponentially 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 epsilon is prohibitive.