An Optimal Quantum Linear Systems Algorithm

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\mathrm{/}\epsilon ))$ and $\kappa \sqrt{d}(\kappa d\mathrm{/}\epsilon {)}^{o(1)}$, while the best known lower bounds were $\mathrm{\Omega }(\kappa \log (1\mathrm{/}\epsilon ))$ and $\mathrm{\Omega }(\kappa \sqrt{d})$. We improve these bounds and show that the complexity of the QLSP is $\mathrm{\Theta }(\kappa \sqrt{d}\log (1\mathrm{/}\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.