A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers
Abstract
Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number κ, the sparsity s of the input matrix, and the target precision ε. The dependence on κ and ε is already well understood through the lower bound Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity s is included, however, the expected lower bound has long been conjectured to be Ω(κ√slog(1/ε)). Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound Ω(κ√s) for constant error ε. In this work, we complete the picture and prove the full joint lower bound Ω(κ√slog(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
Related
- Sparse block encoding with low subnormalisation for quantum linear solvers on unstructured meshes
- An analysis of iterative refinement for quantum linear system solvers
- Simultaneously Query-Optimal Quantum Linear-System Algorithm
- Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers
- Quantum linear solvers for quantum chemistry: prospects of exponential quantum advantage
BibTeX
@misc{patel2026nearoptimal,
title = {{A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers}},
author = {Dhrumil Patel},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.22445},
eprint = {2609.22445},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.22445},
}
RIS
TY - UNPB
TI - A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers
AU - Dhrumil Patel
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.22445
UR - https://arxiv.org/abs/2609.22445
AB - Quantum linear system solvers form one of the central algorithmic primitives in quantum computing, with applications ranging from differential equations and optimization to machine learning. Their cost is commonly measured through query complexity, which counts the number of oracle calls needed to access the input matrix. In the sparse-access model, this complexity is governed by three parameters: the condition number κ, the sparsity s of the input matrix, and the target precision ε. The dependence on κ and ε is already well understood through the lower bound Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity s is included, however, the expected lower bound has long been conjectured to be Ω(κ√slog(1/ε)). Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound Ω(κ√s) for constant error ε. In this work, we complete the picture and prove the full joint lower bound Ω(κ√slog(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
ER -