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\rangle$ of linear system $Ax=| b \rangle$ to accuracy $\epsilon$ with complexity independent of the condition number $\kappa=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(\kappa_{\mathrm{eff}}\operatorname{polylog}\left(\frac{\kappa_{\mathrm{eff}}}{\epsilon}\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $\kappa_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{\epsilon^{1/t}}$ for positive even integer $t$ and $\kappa_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{\epsilon^{1/t}}$ for positive odd $t$, overcoming the $\kappa$-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity $3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}{\epsilon}$ 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.

50 pages, 3 figures. v2: improved filtering-based solver with leading-order query cost $6\frac{\|A^{-1\dagger}|x\rangle\|}ε\ln\left(\frac{1}ε\right)$ to $3\frac{\|A^{-1\dagger}|x\rangle\|}ε$

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Numerical Analysis (math.NA)

arXiv:2607.07691 [quant-ph]

(or arXiv:2607.07691v2 [quant-ph] for this version)