Skip to content
Preprint

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

Sep 2026 · 5 citations · ⚡ 1 influential · 9 references
Physics

TL;DR

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.

View source

Similar papers

Preprint Oct 2026

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight

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
Preprint Sep 2026

Simultaneously Query-Optimal Quantum Linear-System Algorithm

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
Preprint Sep 2026

An Optimal Quantum Linear Systems Algorithm

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
Preprint Oct 2026

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

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...

Ze-Kun Ye · 0 citations
Preprint Sep 2026

Breaking the Multiplicative Overhead in Quantum Entropy Estimation

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...

Jun-Xiang Huang, Chen-Yang Li, Lu-Fan Zhang et al. · 1 citation · ⚡1
Preprint Oct 2026

Tight bounds for hybrid quantum-classical query algorithms

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.