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 $\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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35660
curl -X POST /api/v1/records/arxiv/2609.35660/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35660/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'