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

TLDR

Harrow, Hassidim, and Lloyd introduced a quantum algorithm that outputs a state proportional to the solution of a linear system, running in time poly(log N, 1/ε) for sparse, well‑conditioned matrices. This work seeks to reduce the algorithm’s dependence on precision from 1/ε to poly(log (1/ε)). The authors accomplish this by implementing arbitrary operators via Fourier or Chebyshev series, thereby avoiding the costly quantum phase estimation step. The resulting algorithm achieves an exponential improvement in precision dependence while preserving the original scaling with respect to other parameters.

Abstract

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