This work proves the full joint lower bound $\Omega(\kappa\sqrt{s}\log(1/\varepsilon)$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
Abstract
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 $\kappa$, the sparsity $s$ of the input matrix, and the target precision $\varepsilon$. The dependence on $\kappa$ and $\varepsilon$ is already well understood through the lower bound $\Omega(\kappa\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 $\Omega(\kappa\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 $\Omega(\kappa\sqrt{s})$ for constant error $\varepsilon$. In this work, we complete the picture and prove the full joint lower bound $\Omega(\kappa\sqrt{s}\log(1/\varepsilon))$ in the sparse-access model, thereby establishing the anticipated dependence on all three parameters simultaneously.
Quantum algorithms for linear algebra that access a matrix $A$ through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to $A$, return sampling and query access to an ap...
Shouvanik Chakrabarti, Dylan Herman, J. Kim et al.· 0 citations
A quantum linear-system algorithm that prepares the normalized solution to error $\varepsilon$ using simultaneously $ O\left(\kappa\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left({\kappa}/{s}\right)$ queries to $U_b$.
Minbo Gao, Zheng-Feng Ji, Cheng-Hua Liu· 0 citations
In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $\kappa$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $\epsilon$-approximation to the quantum state proportional to the solution...
Carlos Bravo-Prieto, A. Harrow, Robin Kothari· 7 citations· ⚡1
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This...
The von Neumann, Tsallis, and R\'enyi entropies are fundamental measures of quantum information. A common estimation strategy multiplies the worst-case costs of spectral transformation and statistical readout, leaving gaps to query lower bounds. We reduce this overhead with multi-level algorithms that use local normali...
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation...
A. Ambainis, A. Gilyén, M. Kokainis· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.