Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This work resolves a longstanding open problem in quantum computing by establishing the exact query complexity of the quantum linear systems problem (QLSP) for $d$-sparse $N \times N$ matrices with condition number $\kappa$ and precision $\varepsilon$. Pinpointing the theoretical limits of QLSP is essential because it forms the algorithmic backbone for proposed quantum advantages across optimization, differential equation solvers, and machine learning. The authors prove an optimal tight bound of $\Theta(\kappa \sqrt{d}\log(1/\varepsilon))$ queries while simultaneously solving an open problem by Berry and Childs, showing any $N \times N$ unitary can be implemented with bounded error using $O(\sqrt{N})$ matrix entry queries.
After fifteen years of algorithmic trade-offs, the quantum linear systems problem is finally solved with a provably tight query complexity of $\Theta(\kappa \sqrt{d}\log(1/\varepsilon))$.
In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-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(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. 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.