{"id":"arxiv/2609.35660","url":"https://arxiv.org/abs/2609.35660","tags":["quant-ph"],"score":0,"title":"An Optimal Quantum Linear Systems Algorithm","domain":"quant-ph","source":"arxiv","authors":["Carlos Bravo-Prieto","Aram W. Harrow","Robin Kothari"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}