Faster Quantum Linear System Solver Beyond the Condition Number

Jul 16, 2026

Spectral condition number κ is a common worst-case cost metric for quantum linear system solvers, yet it can overestimate runtime for typical instances. Two quantum algorithms are presented to prepare the normalized solution of Ax = |b⟩ to accuracy ε with complexity independent of κ, using a standard block-encoding input model and an affine dilation model to refine query complexity. A truncation-based solver controls an effective condition number family, and a filtering-based solver uses a simple mechanism with favorable leading-order cost and an accompanying solution-norm estimator.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages52

Reading Time2 h 11 min

Introduction

Quantum linear system solvers

Main result

Block encoding and affine dilation

Solver based on effective truncation of linear system

Solver based on filtering with effective gap

Quantum linear system problem and input models

Standard input model

Affine dilation model

Quantum linear system problem

Beyond-κ solver based on effective truncation of linear system

Effective condition number

Bounds on the effective condition number

Beyond-κ solver based on filtering with effective gap

Effective gap lemma

Eigenstate filtering over unit circle

Beyond-κ solution norm estimation

Discussion

arXiv :2607 .07691v1 [ quant-ph] 8 Jul 2026 Faster quantum linear system solver beyond the condition number Alexander M. Dalzell 1 , Jianqiang Li2 , and Yuan Su 1 1 AWS Center for Quantum Computing, Pasadena, CA 91106, USA 2 Department of Computer Science, Rice University, Houston, TX 77005, USA 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 of linear system Ax = |b⟩ to accuracy ϵ with complexity independent of the condition number κ = ∥A∥ 􀀍A −1 􀀍 . We focus on the standard input model where the coefficient matrix A is accessed through a block encoding oracle and the initial vector |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 the preparation of |b⟩ and O 􀀀κeff polylog 􀀀 ~~κe~~ϵ~~ff~~ 􀀁􀀁 queries to the block encoding of A. We prove a family of upper bounds on the effective condition number κeff , including κeff ≤ ∥~~ ~~(AAx∥)tt/ϵ21x/t∥1/t for positive even integer t and κeff ≤ ∥A~~ ~~−1†(†x1)t(tϵ1t)/2x~~ ~~∥1/t for positive odd t, going beyond the naive estimate in terms of κ . Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 6 ~~ ~~∥A∥−x†ϵx~~ ~~∥ ln 􀀀 ~~ 1~~ϵ􀀁 to leading order when the solution norm ∥x∥ 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, which has runtime O 􀀒 ~~ ~~∥−x†ϵx~~2~~∥ 􀀓 if ∥x∥ is known and O 􀀒 ~~ ~~∥A~~ ~~−~~ ~~1†ϵx~~2~~∥~~ ~~∥x∥2 􀀓 otherwise. This enables faster quantum linear system solving beyond the condition number, bringing prohibitively illconditioned systems closer to feasibility. Contents 1 Introduction 3 1.1 Quantum linear system solvers .............................. 3 1.2 Main result ......................................... 4 1.3 Block encoding and affine dilation ............................ 6 1.4 Solver based on effective truncation of linear system .................. 7 1.5 Solver based on filtering with effective gap ........................ 9 2 Quantum linear system problem and input models 11 2.1 Standard input model ................................... 11 2.2 Affine dilation model .................................... 12 2.3 Quantum linear system problem ............................. 13 3 Beyond-κ solver based on effective truncation of linear system 15 3.1 Effective condition number ................................ 15 3.2 Bounds on the effective condition number ........................ 18 3.3 Analysis of beyond-κ solver based on effective matrix truncation ........... 21 3.4 Oracle for effective state truncation ............................ 23 3.5 Analysis of beyond-κ solver based on effective state truncation ............ 25 4 Beyond-κ solver based on filtering with effective gap 27 4.1 Block encoding and constrained orthogonal decomposition ............... 28 4.2 Effective gap lemma .................................... 30 4.3 Eigenstate filtering over unit circle ............................ 31 4.4 Constant-prefactor analysis of beyond-κ solver based on filtering ........... 34 4.5 Beyond-κ solution norm estimation ............................ 37 5 Discussion 39 A Analysis of Li’s beyond-κ solver in the standard input model 42 B Analysis of beyond-κ solvers in the affine dilation model 43 B.1 Analysis of truncation-based solvers in the affine dilation model ............ 43 B.2 Analysis of filtering-based solver in the affine dilation model .............. 44

FAQs

Why can the spectral condition number overestimate quantum linear system runtime?

It is a worst-case metric, but it may be much larger than what typical problem instances effectively require, so it can overestimate actual runtime.

What do the two proposed algorithms achieve for solving Ax = |b⟩?

They output the normalized solution to accuracy ε with complexity independent of the condition number κ, under a standard block-encoding model and an affine dilation model.

How do truncation-based and filtering-based solvers differ in approach?

The truncation-based solver uses effective truncation to bound an effective condition number, while the filtering-based solver uses an eigenstate filtering mechanism with a simple construction and a favorable runtime prefactor.

Jul 16, 2026

Upload by Clementine