Multiplicative sparse-access lower bound for quantum linear systems
- Field
- Topics
Problem
Does sparse-oracle quantum linear-system solving require \(\Omega(\kappa\sqrt{s}\log(1/\varepsilon))\) queries in the worst case?
Let \(A\) be an invertible \(D\times D\) matrix with at most \(s\) nonzero entries per row and column, \(\|A\|\leq1\), and smallest singular value at least \(1/\kappa\). Given standard sparse-location and entry-value oracles for \(A\) and an efficiently prepared state \(|b\rangle\), the task is to prepare a state within Euclidean distance \(\varepsilon\) of
For \(s\geq3\), \(\kappa\geq2\), \(0<\varepsilon<1/10\), sufficiently large \(D\), and success probability at least \(2/3\), is the worst-case query complexity necessarily
Equation (2) asks for a joint lower bound for the state-preparation task in Eq. (1).
Source
The question is explicitly posed or retained as open in the cited primary literature [Mori26]. The statement is rewritten here to make its hypotheses and success criterion self-contained.
Progress
2026 lower-bound advance. Mori, Kikuchi, Benedetti, and Rosenkranz rigorously prove \(\Omega(\kappa\sqrt{s})\) at constant error and give a proof of the \(\Omega(\kappa\log(1/\epsilon))\) dependence. Their latest revision explicitly leaves the multiplicative three-parameter bound unresolved. [Mori26]
The two inequalities alone yield only
\begin{equation} \Omega\!\left(\kappa\max\left\{\sqrt{s},\log(1/\epsilon)\right\}\right), \tag{3} \end{equation}not their product. This distinction is a logical issue, not a hidden logarithmic convention.
The displayed definitions, constraints, and target bounds are recorded in Eqs. (3).
March 23, 2026. Low and Su optimize calls to the initial-state preparation procedure in a linear-system algorithm. Optimality for that oracle is not the missing joint lower bound for sparse matrix access. [Low26]
July 8, 2026. Dalzell, Li, and Su present a solver exploiting instance-dependent structure beyond a single worst-case condition number. Faster performance on favorable instances does not contradict the worst-case conjecture above. [Dalzell26]
Why the natural composition argument is insufficient. Section 5 of [Mori26] explains that introducing precision through their unbounded-error Boolean reduction loses the desired sparsity contribution. Its closing discussion explicitly reserves the joint bound for future work.
Retained as open, with unusually direct and recent primary-source support.
Comment
This problem is an explicit folklore conjecture, restated as open in the August 24, 2026 revision of [Mori26].
The conjecture asks whether three sources of difficulty can coexist multiplicatively in a single hard family. It cannot be settled by pointing to separate instances that are hard for separate reasons.
A potentially useful research objective is a state-conversion or adversary construction preserving both sparse-search hardness and high-precision hardness under the same normalization. Oracle implementation must be charged explicitly: a lower bound in a block-encoding model does not automatically become the same lower bound in sparse access. Likewise, an algorithm advertised as “optimal in \(\kappa\) and \(\epsilon\)” need not settle the joint \(s\) dependence.
References
- [Mori26]
- Hitomi Mori, Yuta Kikuchi, Marcello Benedetti, and Matthias Rosenkranz. Sparsity-dependent Complexity Lower Bound of Quantum Linear System Solvers. Quantum Science and Technology 11, 035063 (2026); August 24, 2026. See the abstract, oracle definition, and Section 5.link
- [Low26]
- Guang Hao Low and Yuan Su. Quantum linear system algorithm with optimal queries to initial state preparation. Quantum 10, 2041, March 23, 2026; arXiv:2410.18178.link
- [Dalzell26]
- Alexander M. Dalzell, Jianqiang Li, and Yuan Su. Faster quantum linear system solver beyond the condition number. July 8, 2026, preprint.arXiv