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 κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of A =. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κd (1/ε)) and κ sqrt d(κd/ε) o(1), while the best known lower bounds were Ω(κ (1/ε)) and Ω(κ sqrt d). We improve these bounds and show that the complexity of the QLSP is Θ(κ sqrt d (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.