Faster quantum linear system solver beyond the condition number
Abstract
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution |x⟩ of linear system Ax=| b ⟩ to accuracy ε with complexity independent of the condition number κ=lVert A−1rVert. We focus on the standard input model where A is accessed through a block encoding and | b ⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes A and | b ⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to | b ⟩ and O(κeffpolylog(κeff/ε)) queries to A. We prove a family of upper bounds on the effective condition number, including κeff≤(lVert(A† A)−t/2|x⟩rVert1/t)/ε1/t for positive even integer t and κeff≤(lVert A−1†(A† A)−(t−1)/2|x⟩rVert1/t)/ε1/t for positive odd t, overcoming the κ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3(lVert A−1†|x⟩rVert)/ε to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.
Related
- A Preconditioned Quantum Linear Solver for Periodic Two-Phase Heat Conduction with Mesh-Independent Condition Number
- Faster Linear Programming with √(rank) Linear System Solves
- A Roe-type approximate-flux Riemann solver without linear system resolution and application to lagrangian solid mechanics
- An analysis of iterative refinement for quantum linear system solvers
- Newton Steps are Faster for Linear Complementarity Problems
BibTeX
@misc{dalzell2026faster,
title = {{Faster quantum linear system solver beyond the condition number}},
author = {Alexander M. Dalzell and Jianqiang Li and Yuan Su},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.07691},
eprint = {2607.07691},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.07691},
note = {CC BY-SA 4.0},
}
RIS
TY - UNPB
TI - Faster quantum linear system solver beyond the condition number
AU - Alexander M. Dalzell
AU - Jianqiang Li
AU - Yuan Su
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2607.07691
UR - https://arxiv.org/abs/2607.07691
AB - The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution |x⟩ of linear system Ax=| b ⟩ to accuracy ε with complexity independent of the condition number κ=lVert A^−1rVert. We focus on the standard input model where A is accessed through a block encoding and | b ⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes A and | b ⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to | b ⟩ and O(κ_effpolylog(κ_eff/ε)) queries to A. We prove a family of upper bounds on the effective condition number, including κ_eff≤(lVert(A^† A)^−t/2|x⟩rVert^1/t)/ε^1/t for positive even integer t and κ_eff≤(lVert A^−1†(A^† A)^−(t−1)/2|x⟩rVert^1/t)/ε^1/t for positive odd t, overcoming the κ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3(lVert A^−1†|x⟩rVert)/ε to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.
ER -