Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2601.16697 · Quantum Science and Technology

Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers

Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, Matthias Rosenkranz

quant-phSubmitted Jan 23, 2026• Announced Jan 26, 2026• 0 citations
v1 · Jan 23, 2026v2 · Aug 24, 2026
arXivHTMLPDF

Abstract

Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number $κ$ and sparsity $s$ of the linear system, and the target error $ε$. To date, the best known query-complexity lower bound is $Ω(κ\log(1/ε))$, which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity $s$ of the linear system, it has become folklore that it should read as $Ω( κ\sqrt{s}\log(1/ε))$. In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of $Ω(κ\sqrt{s})$ for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters $κ,s,ε$ remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.

Journal reference
Quantum Sci. Technol. 11 035063 (2026)
DOI
10.1088/2058-9565/ae89e0

Related papers

A Near-Optimal Joint Lower Bound for Sparse Quantum Linear System Solvers

Dhrumil Patel

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 $\varepsilon$. The dependence on $κ$ and $\varepsilon$ is already well understood through the lower bound $Ω(κ\log(1/\varepsilon))$, 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 $Ω(κ\sqrt{s}\log(1/\varepsilon))$. Recent work by Mori et al. [Quantum Sci. Tech. 11 035063 (2026)] made an important step towards this goal by establishing the lower bound $Ω(κ\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $Ω(κ\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.

quant-pharXiv:2609.22445•Sep 22, 2026•0 citations

Root-sparsity scaling for Hamiltonian simulation, differential equations and linear-system solvers

Dominic W. Berry, Abhishek Rawat, Sophia Simon +1 more

We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an $s$-sparse Hermitian matrix with row and column Euclidean norms bounded by $η$, evolution for time $t$ to error $ε$ uses $\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))$ queries, where $τ=η|t|$. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in $\sqrt{s}τ$ and $\log(1/ε)$. For dissipative linear differential equations we obtain $\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))$ queries, where $τ$ is the evolution time multiplied by a norm bound, $\bar g$ bounds the ratio of combined input and source norms to the final-solution norm, and $C$ is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give $\mathcal{O}(κ\sqrt{s}\log(1/ε))$ queries when $\|A\|\le1$ and $\|A^{-1}\|\leκ$, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.

quant-pharXiv:2610.02939•Oct 5, 2026•0 citations

Square-Root Sparsity and the Closure of the Quantum Linear Systems Query Gap: An Anatomical, Comparative, and Epistemic Review of Bravo-Prieto, Harrow, and Kothari

Syed Muntasir Mamun

This review anatomises Bravo-Prieto, Harrow and Kothari (2026) on the query complexity of the quantum linear systems problem in the standard sparse-matrix oracle model, which they show is Θ(κ √d log(1/ε)). The upper bound is a reduction: after an enlargement and per-entry normalisation, a contraction whose inverse norm is at most 5κ √d is handed to the existing block-encoded solver of Costa, An, Sanders, Su, Babbush and Berry (2022), giving O(κ √d log(1/ε)) sparse-oracle queries. The matching lower bound multiplies unstructured search by a parity of length Θ(κ log(1/ε)); the quantum XOR lemma of Lee and Roland (2012) converts a vanishing advantage into the joint query lower bound. A corollary implements an N × N unitary from its entries with O(√N log(1/ε)) queries, closing the black-box unitary question posed by Berry and Childs (2012). Primary source: Bravo-Prieto, C., Harrow, A.W. and Kothari, R. (2026), An Optimal Quantum Linear Systems Algorithm, arXiv:2609.35660. This deposit is a KSCCN review by Syed Muntasir Mamun, not the BHK paper. KSCCN review article, 3 October 2026. Dr. Syed Muntasir Mamun, ORCID 0000-0001-6845-2853. The views expressed are those of the author.

•Oct 3, 2026•0 citations

Simultaneously Query-Optimal Quantum Linear-System Algorithm

Minbo Gao, Zhengfeng Ji, Chenghua Liu

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$, we give a quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $Ω(κ\log(1/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

quant-pharXiv:2609.33686•Sep 29, 2026•0 citations

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.

quant-pharXiv:2609.35660•Sep 29, 2026•0 citations

Square-Root Sparsity and the Closure of the Quantum Linear Systems Query Gap: An Anatomical, Comparative, and Epistemic Review of Bravo-Prieto, Harrow, and Kothari

Syed Muntasir Mamun

This review anatomises the argument of Bravo-Prieto, Harrow and Kothari (2026), hereafter BHK, that the query complexity of the quantum linear systems problem (QLSP) in the standard sparse-matrix oracle model is ( d log(1/ )). The paper closes a gap left by two incomparable upper bounds the discrete-adiabatic bound O( d log(1/ )) of Costa, An, Sanders, Su, Babbush and Berry (2022) and the spectral-norm simulation bound d ( d/ )o(1) of Low (2019) and by two partial lower bounds, ( log(1/ )) and ( d). The upper bound is not a new inversion primitive. It is a linear-algebraic enlargement: the factorisation A/ d = F T is split into two equations, each matrix entry is normalised separately, and the resulting contraction M, with M 5 d, is handed to an existing block-encoded solver. The lower bound multiplies unstructured search by a parity of length ( log(1/ )), with the quantum XOR lemma of Lee and Roland (2012) converting a vanishing advantage into a joint query lower bound. A corollary resolves the Berry and Childs (2012) question on black-box unitary implementation at O( N log(1/ )). The review reconstructs the proof anatomy, states pros and cons with explicit scope conditions, and compares BHK with fifteen neighbouring models spanning phase estimation, variable-time amplification, linear combinations of unitaries, adiabatic schedules, quantum singular value transformation, dense QRAM access, preconditioning, and the concurrent lower bound of Patel (2026). Also available on Academia.edu: https://www.academia.edu/attachments/134662881/download_file?s=portfolio

•Oct 3, 2026•0 citations
Quantum linear system (QLS) solvers are a fundamental class of quantum algorithms used in many potential quantum computing applications, including machine learning and solving differential equations. The performance of quantum algorithms is often measured by their query complexity, which quantifies the number of oracle calls required to access the input. The main parameters determining the complexity of QLS solvers are the condition number κκκ and sparsity sss of the linear system, and the target error εεε. To date, the best known query-complexity lower bound is Ω(κlog⁡(1/ε))Ω(κ\log(1/ε))Ω(κlog(1/ε)), which establishes the optimality of the most recent QLS solvers. The original proof of this lower bound is attributed to Harrow and Kothari, but their result is unpublished. Furthermore, when discussing a more general lower bound including the sparsity sss of the linear system, it has become folklore that it should read as Ω(κslog⁡(1/ε))Ω( κ\sqrt{s}\log(1/ε))Ω(κs​log(1/ε)). In this work, we establish the rigorous lower bound capturing the sparsity dependence of QLS. We prove the lower bound of Ω(κs)Ω(κ\sqrt{s})Ω(κs​) for any quantum algorithm that solves QLS with constant error. While the dependence on all parameters κ,s,εκ,s,εκ,s,ε remains an open problem, our result provides a crucial stepping stone toward the complete characterization of QLS complexity.
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 sss of the input matrix, and the target precision ε\varepsilonε. The dependence on κκκ and ε\varepsilonε is already well understood through the lower bound Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)), which matches the best known scaling in these parameters. Once the sparsity sss is included, however, the expected lower bound has long been conjectured to be Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(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)Ω(κ\sqrt{s})Ω(κs​) for constant error ε\varepsilonε. In this work, we complete the picture and prove the full joint lower bound Ω(κslog⁡(1/ε))Ω(κ\sqrt{s}\log(1/\varepsilon))Ω(κs​log(1/ε)) in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
We give quantum algorithms for Hamiltonian simulation, linear differential equations, and linear systems with square-root dependence on sparsity. For an sss-sparse Hermitian matrix with row and column Euclidean norms bounded by ηηη, evolution for time ttt to error εεε uses O(sτ+sτlog⁡(1/ε)+log⁡(1/ε))\mathcal{O}(\sqrt{s}τ+\sqrt{sτ\log(1/ε)}+\log(1/ε))O(s​τ+sτlog(1/ε)​+log(1/ε)) queries, where τ=η∣t∣τ=η|t|τ=η∣t∣. The same bound holds for time-dependent Hamiltonians with coherent time-indexed sparse access and certified time discretisation. Our construction combines an exact entrywise representation with Cayley transducers. A joint lower bound nearly matches the time, sparsity, and precision dependence, ruling out a uniformly additive bound in sτ\sqrt{s}τs​τ and log⁡(1/ε)\log(1/ε)log(1/ε). For dissipative linear differential equations we obtain O(gˉ[s(τ+τ)+1]log⁡(Cgˉ/ε))\mathcal{O}(\bar g[\sqrt{s}(τ+\sqrtτ)+1]\log(C\bar g/ε))O(gˉ​[s​(τ+τ​)+1]log(Cgˉ​/ε)) queries, where τττ is the evolution time multiplied by a norm bound, gˉ\bar ggˉ​ bounds the ratio of combined input and source norms to the final-solution norm, and CCC is an absolute constant. We sharpen this bound by separating Hamiltonian and dissipative components, and treat general constant generators. Lower bounds capture joint parameter dependence for time-dependent equations and precision hardness for constant positive semidefinite dissipation. For linear systems, a Cayley walk and Chebyshev filter give O(κslog⁡(1/ε))\mathcal{O}(κ\sqrt{s}\log(1/ε))O(κs​log(1/ε)) queries when ∥A∥≤1\|A\|\le1∥A∥≤1 and ∥A−1∥≤κ\|A^{-1}\|\leκ∥A−1∥≤κ, and we give an alternative proof of a matching joint lower bound. We also give gate-efficient implementations of time-independent Hamiltonian simulation and the dissipative ODE solver, including Lipschitz time dependence, retaining the query bounds with polylogarithmic overhead in inverse precision given efficient entry decoding, arithmetic, and required source preparations.
This review anatomises Bravo-Prieto, Harrow and Kothari (2026) on the query complexity of the quantum linear systems problem in the standard sparse-matrix oracle model, which they show is Θ(κ √d log(1/ε)). The upper bound is a reduction: after an enlargement and per-entry normalisation, a contraction whose inverse norm is at most 5κ √d is handed to the existing block-encoded solver of Costa, An, Sanders, Su, Babbush and Berry (2022), giving O(κ √d log(1/ε)) sparse-oracle queries. The matching lower bound multiplies unstructured search by a parity of length Θ(κ log(1/ε)); the quantum XOR lemma of Lee and Roland (2012) converts a vanishing advantage into the joint query lower bound. A corollary implements an N × N unitary from its entries with O(√N log(1/ε)) queries, closing the black-box unitary question posed by Berry and Childs (2012). Primary source: Bravo-Prieto, C., Harrow, A.W. and Kothari, R. (2026), An Optimal Quantum Linear Systems Algorithm, arXiv:2609.35660. This deposit is a KSCCN review by Syed Muntasir Mamun, not the BHK paper. KSCCN review article, 3 October 2026. Dr. Syed Muntasir Mamun, ORCID 0000-0001-6845-2853. The views expressed are those of the author.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UAU_AUA​ and the right-hand side through a state-preparation oracle UbU_bUb​. The optimal query complexities of these two oracles are known separately: O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) queries to UAU_AUA​ and O(κ/s)O(κ/s)O(κ/s) queries to UbU_bUb​, where s=α∥A−1b∥s=α\|A^{-1}b\|s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of sss, we give a quantum linear-system algorithm that prepares the normalized solution to error ε\varepsilonε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UAU_AUA​ and O(κ/s)O\left(κ/{s}\right)O(κ/s) queries to UbU_bUb​. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog⁡(1/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)) matrix queries and Ω(κ/s)Ω(κ/s)Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
In the quantum linear systems problem (QLSP), we are given query access to a ddd-sparse N×NN\times NN×N matrix AAA with condition number κκκ, and the ability to prepare a quantum state proportional to a vector b⃗\vec bb. The goal is to output an εεε-approximation to the quantum state proportional to the solution x⃗\vec xx of Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog⁡(1/ε))O(κd\log(1/ε))O(κdlog(1/ε)) and κd(κd/ε)o(1)κ\sqrt d(κd/ε)^{o(1)}κd​(κd/ε)o(1), while the best known lower bounds were Ω(κlog⁡(1/ε))Ω(κ\log(1/ε))Ω(κlog(1/ε)) and Ω(κd)Ω(κ\sqrt d)Ω(κd​). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog⁡(1/ε))Θ(κ\sqrt d\log(1/ε))Θ(κd​log(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×NN\times NN×N unitary can be implemented with bounded error using O(N)O(\sqrt N)O(N​) queries to its matrix entries.
This review anatomises the argument of Bravo-Prieto, Harrow and Kothari (2026), hereafter BHK, that the query complexity of the quantum linear systems problem (QLSP) in the standard sparse-matrix oracle model is ( d log(1/ )). The paper closes a gap left by two incomparable upper bounds the discrete-adiabatic bound O( d log(1/ )) of Costa, An, Sanders, Su, Babbush and Berry (2022) and the spectral-norm simulation bound d ( d/ )o(1) of Low (2019) and by two partial lower bounds, ( log(1/ )) and ( d). The upper bound is not a new inversion primitive. It is a linear-algebraic enlargement: the factorisation A/ d = F T is split into two equations, each matrix entry is normalised separately, and the resulting contraction M, with M 5 d, is handed to an existing block-encoded solver. The lower bound multiplies unstructured search by a parity of length ( log(1/ )), with the quantum XOR lemma of Lee and Roland (2012) converting a vanishing advantage into a joint query lower bound. A corollary resolves the Berry and Childs (2012) question on black-box unitary implementation at O( N log(1/ )). The review reconstructs the proof anatomy, states pros and cons with explicit scope conditions, and compares BHK with fifteen neighbouring models spanning phase estimation, variable-time amplification, linear combinations of unitaries, adiabatic schedules, quantum singular value transformation, dense QRAM access, preconditioning, and the concurrent lower bound of Patel (2026). Also available on Academia.edu: https://www.academia.edu/attachments/134662881/download_file?s=portfolio