An Optimal Quantum Linear Systems Algorithm
Abstract
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N× 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 Ax⃗=b⃗. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κ√d(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κ√d). We improve these bounds and show that the complexity of the QLSP is Θ(κ√dlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N× N unitary can be implemented with bounded error using O(√N) queries to its matrix entries.
Related
- Simultaneously Query-Optimal Quantum Linear-System Algorithm
- A QSVT-Based Quantum Jacobi Algorithm for Linear Systems with Application to the Poisson Equation
- Linear combination of Schrödingerization for quantum linear systems with optimal matrix-query complexity
- Mirror subspace diagonalization: a real-time quantum Krylov algorithm with near-optimal sampling cost
- Chern-number estimation: nearly optimal quantum algorithm and provable quantum speedup
BibTeX
@misc{bravoprieto2026optimal,
title = {{An Optimal Quantum Linear Systems Algorithm}},
author = {Carlos Bravo-Prieto and Aram W. Harrow and Robin Kothari},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35660},
eprint = {2609.35660},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35660},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - An Optimal Quantum Linear Systems Algorithm
AU - Carlos Bravo-Prieto
AU - Aram W. Harrow
AU - Robin Kothari
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35660
UR - https://arxiv.org/abs/2609.35660
AB - In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N× 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 Ax⃗=b⃗. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κ√d(κd/ε)^o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κ√d). We improve these bounds and show that the complexity of the QLSP is Θ(κ√dlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N× N unitary can be implemented with bounded error using O(√N) queries to its matrix entries.
ER -