An Optimal Quantum Linear Systems Algorithm

Abstract

In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $\kappa$, and the ability to prepare a quantum state proportional to a vector $\vec{b}$. The goal is to output an $\epsilon$-approximation to the quantum state proportional to the solution $\vec{x}$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(\kappa d\log (1/\epsilon ))$ and $\kappa \sqrt{d}(\kappa d/\epsilon {)}^{o(1)}$, while the best known lower bounds were $\Omega (\kappa \log (1/\epsilon ))$ and $\Omega (\kappa \sqrt{d})$. We improve these bounds and show that the complexity of the QLSP is $\Theta (\kappa \sqrt{d}\log (1/\epsilon ))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt{N})$ queries to its matrix entries.

20 pages