Quantum linear systems algorithm with exponentially improved dependence on precision

TitleQuantum linear systems algorithm with exponentially improved dependence on precision
Publication TypeJournal Article
Year of Publication2015
AuthorsChilds, AM, Kothari, R, Somma, RD
Date Published2015/11/07
Abstract

Harrow, Hassidim, and Lloyd showed that for a suitably specified N×N matrix A and 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(logN,1/ϵ), where ϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(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.

URLhttp://arxiv.org/abs/1511.02306