REVIEW
An Optimal Quantum Linear Systems Algorithm
Quantum Physics · Submitted 28 Sep 2026 · 23 references
Pith's verdict: Upper bound is verified and clean; the whole paper now turns on the one-line citation for Lemma 12 in the lower bound.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The quantum linear systems problem has query complexity exactly $\Theta(\kappa\sqrt d \log(1/\epsilon))$: a new upper bound that block-encodes an enlarged system in $O(1)$ queries meets a history-state lower bound that multiplies the…
The reading
What carries the argument
The load-bearing objects are the enlarged linear system and the clock-unitary history-state construction. For the upper bound, the matrix $M$ splits the equation $(F^\dagger T)\vec u = \vec b$, where $F^\dagger T = A/\sqrt d$, into the two equations $z = T\vec u$ and $F^\dagger z = \vec b$ by introducing the intermediate vector $z$, which assigns to each solution variable $u_j$ the $d$ copies $z_{ij} = u_j/\sqrt d$ over its listed equation slots $i \in N(j)$; this enlarged system can be block encoded exactly with $O(1)$ queries even though the row-loading map $F$ cannot, and the column-normalization operator $Q$ satisfies $\lVert QT\rVert \le \sqrt 2$, which bounds the inverse norm and keeps solution recovery at constant probability. For the lower bound, the operator $A = (I - \alpha U)/2$ with $\alpha = 1 - 2/\kappa$ built from a clock unitary $U$ makes the solution proportional to a weighted superposition of the circuit's intermediate states, so the idling interval that stores the output survives for a duration governed jointly by $\kappa$ and $\epsilon$; composing $R = \Theta(\kappa \log(1/\epsilon))$ parity-of-search instances then requires the quantum XOR lemma to certify hardness at exponentially small advantage.
Extended reading notes
Core claim
The paper's central claim, Theorem 1, is that the QLSP has query complexity $\Theta(\kappa\sqrt d \log(1/\epsilon))$ in the sparse-matrix oracle model: no quantum algorithm beats $O(\kappa\sqrt d \log(1/\epsilon))$ queries, and the paper's own algorithm achieves it. The algorithmic side constructs, with $O(1)$ oracle queries, an exact block encoding of an enlarged invertible matrix $M$ whose inverse norm is $O(\kappa\sqrt d)$ and whose normalized solution contains the desired $A^{-1}\vec b/\lVert A^{-1}\vec b\rVert$ as a directly measurable component; recovery succeeds with constant probability because a key lemma gives $\lVert QT\rVert \le \sqrt 2$. The construction works around the unstructured-search obstruction to implementing the row-loading map $F$ by replacing each solution variable with $d$ copies, one per listed equation slot, and letting the solver perform the summation. The lower bound, Theorem 10, converts a circuit into a linear system whose solution is a geometrically weighted history state, threads $\kappa$ and $\epsilon$ into the length of a circuit that XORs $R = \Theta(\kappa \log(1/\epsilon))$ independent search instances each of size $\Theta(d)$, and invokes a quantum XOR lemma to show this composed problem needs $\Omega(R\sqrt d)$ queries even when the solver's advantage is exponentially small. The same reduction yields an $(O(1),\eta)$ block encoding of any Hermitian $d$-sparse matrix with $O(\sqrt d \log(1/\eta))$ queries, and from it — via the Hermitian dilation of a unitary and robust oblivious amplitude amplification — an $O(\sqrt N)$ bounded-error implementation of any $N\times N$ unitary from its matrix entries.
Load-bearing premise
The joint lower bound — and with it the tight $\Theta(\kappa\sqrt d \log(1/\epsilon))$ — depends on Lemma 12's claim that the Lee–Roland quantum XOR lemma gives $\Omega(R\sqrt D)$ hardness for the composed parity-of-search problem even when the allowed advantage over random guessing is exponentially small in $R$, namely $1/2 - e^{-100 R}$; if the published lemma only certifies hardness at constant advantage, the multiplicative $\Omega(\kappa\sqrt d \log(1/\epsilon))$ lower bound does not follow as written.
Editorial extensions
If this is right
- The QLSP query complexity is now characterized exactly as $\Theta(\kappa\sqrt d \log(1/\epsilon))$, so the two incomparable prior upper bounds and the two component lower bounds are all subsumed by a single tight statement.
- Any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries, matching the $\Omega(\sqrt N)$ unstructured-search lower bound and settling the long-standing black-box unitary implementation problem.
- Any Hermitian $d$-sparse matrix admits an $(O(1),\eta)$ block encoding using $O(\sqrt d \log(1/\eta))$ sparse-matrix oracle queries, cutting the sparsity dependence of matrix block-encoding constructions from $O(d)$ to $O(\sqrt d)$.
- The lower bound holds even for flagged solvers allowed to output a random bit on failure, so the $\Omega(\kappa\sqrt d \log(1/\epsilon))$ bound is robust to the solver's success threshold of $1/2$.
Reading between the lines
- The auxiliary-variable reduction is stated for the QLSP, but the mechanism — replacing a product $CD$ by two equations $Cy=b$, $Dx=y$, at the cost of more variables but no additional oracle queries — looks generic; whether it transfers to other sparse-matrix primitives whose bottlenecks are similarly search-hard maps (sparse matrix multiplication, Hamiltonian simulation) is a testable extension th
- Because Theorem 2 gives an $(O(1),\eta)$ block encoding of any Hermitian $d$-sparse matrix at $O(\sqrt d \log(1/\eta))$ queries, composing it with standard block-encoding arithmetic (addition, multiplication, inversion) should lower the query counts of downstream quantum algorithms that previously paid $O(d)$ or worse to build their encoding.
- The tight result splits into an algorithmic part (independent of the XOR lemma) and a lower-bound part (dependent on it); recomputing the lower bound with a different function in place of XOR, such as majority, would reveal which features of the $\kappa$, $\sqrt d$, and $\log(1/\epsilon)$ product are robust and which are artifacts of the parity composition.
Original abstract
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 $\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(\kappa d\log(1/\epsilon))$ and $\kappa\sqrt d(\kappa d/\epsilon)^{o(1)}$, while the best known lower bounds were $\Omega(\kappa\log(1/\epsilon))$ and $\Omega(\kappa\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $\Theta(\kappa\sqrt d\log(1/\epsilon))$. 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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 $\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(\kappa d\log(1/\epsilon))$ and $\kappa\sqrt d(\kappa d/\epsilon)^{o(1)}$, while the best known lower bounds were $\Omega(\kappa\log(1/\epsilon))$ and $\Omega(\kappa\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $\Theta(\kappa\sqrt d\log(1/\epsilon))$. 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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$. | background 1.00 | 0.11 | 0.02 | asserted 0.96 |
| s1 | The goal is to output an $\epsilon$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. | background 1.00 | 0.09 | 0.03 | asserted 0.98 |
| s2 | Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(\kappa d\log(1/\epsilon))$ and $\kappa\sqrt d(\kappa d/\epsilon)^{o(1)}$, while the best known lower bounds were $\Omega(\kappa\log(1/\epsilon))$ and $\Omega(\kappa\sqrt d)$. | background 0.95 | 0.03 | 0.04 | asserted 1.00 |
| s3 | We improve these bounds and show that the complexity of the QLSP is $\Theta(\kappa\sqrt d\log(1/\epsilon))$. | result 0.90 | 0.96 | 0.93 | asserted 1.00 |
| s4 | 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. | result 0.56 | 0.94 | 0.07 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.