Faster quantum linear system solver beyond the condition number

• URL: http://arxiv.org/abs/2607.07691v1
• Date: Wed, 08 Jul 2026 17:49:40 GMT
• Title: Faster quantum linear system solver beyond the condition number
• Abstract summary: We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
• Score: 50.84794327094274
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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 $ε$ with complexity independent of the condition number $κ=\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(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $κ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive even integer $t$ and $κ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\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 $6\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε\ln\left(\frac{1}ε\right)$ 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 papers

• A Simple Algorithm for Best Separable State [5.5559749120901385]
  We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states.<n>In classical terms, the goal is to maximize $langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$.
  arXiv  Detail & Related papers  (2026-08-10T19:04:15Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Improved sampling algorithms and Poincaré inequalities for non-log-concave distributions [2.959331374750817]
  We show that the query complexity of sampling from $mu$ can be $mathrmpoly(L,d)cdot left(fracLMdepsilon2right)mathcalO(L+1)$, which is in $d$ and $frac1epsilon$ when $L=mathcalO(1)$ and $M=mathrmpoly(d)$.
  arXiv  Detail & Related papers  (2025-07-15T12:06:11Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
  Quantum algorithms for linear systems produce the solution state $A-1|brangle$ by querying two oracles. We present a quantum linear system algorithm making $mathbfThetaleft (1/sqrtpright)$ queries to $O_b$, which is optimal in the success probability. In various applications such as solving differential equations, we can further improve the dependence on $p$ using a block preconditioning scheme.
  arXiv  Detail & Related papers  (2024-10-23T18:00:01Z)
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
  We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$. We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
  arXiv  Detail & Related papers  (2024-08-10T04:26:19Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
  Layered Autonomous Exploration (LAE) is a novel algorithm for AX that attains a sample complexity of $tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12(Srightarrow_LAln12
  arXiv  Detail & Related papers  (2023-02-07T22:58:12Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Fast digital methods for adiabatic state preparation [0.0]
  We present a quantum algorithm for adiabatic state preparation on a gate-based quantum computer, with complexity polylogarithmic in the inverse error.
  arXiv  Detail & Related papers  (2020-04-08T18:00:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.