research
The Quantum Linear-System Query Gap Closed
A new algorithm matched lower bounds in condition number, sparsity and target precision.
Summary
A new algorithm matched lower bounds in condition number, sparsity and target precision.
The quantum linear-systems problem asks for a quantum state proportional to the solution of a sparse matrix equation. Bravo-Prieto, Harrow and Kothari report an algorithm with complexity proportional to the condition number, the square root of sparsity and the logarithm of inverse error, and prove matching lower bounds. They also show that a general unitary can be implemented with bounded error using a square-root number of matrix-entry queries. These are oracle-query results; end-to-end hardware cost includes state preparation and fault-tolerant overhead not captured by the asymptotic statement.
Why it matters
A new algorithm matched lower bounds in condition number, sparsity and target precision.
Limits and context
- These are oracle-query results; end-to-end hardware cost includes state preparation and fault-tolerant overhead not captured by the asymptotic statement.
Key claims
A new algorithm matched lower bounds in condition number, sparsity and target precision.
Qualification: These are oracle-query results; end-to-end hardware cost includes state preparation and fault-tolerant overhead not captured by the asymptotic statement.
Evidence: source-2026-09-29-015
Sources
- arXiv preprint 2609.35660arXiv · primary research
Corrections
No corrections have been recorded for this story.