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.