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

Abstract

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 approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $ρ=\|A\|_F/\|A\|$ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use $\widetilde O(ρ)$ queries, whereas the best dequantized algorithms use $\widetilde O(ρ^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $κ_0>1$, we construct dense linear systems with condition number at most $κ_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $Ω(ρ^4/\logρ)$ classical queries but only $Θ(ρ)$ quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.

The paper asks whether the quartic query-complexity gap between QRAM-based quantum linear algebra and classical dequantized algorithms is necessary. It compares coherent matrix access with classical sampling-and-query access, using the common task of producing one approximate length-squared sample from the solution. Input-data-structure construction costs are excluded. For every fixed condition-number bound $\kappa_0>1$, it constructs dense linear systems with $\rho=\|A\|_F/\|A\|=\Theta(\sqrt n)$ requiring $\Omega(\rho^4/\log\rho)$ classical queries at sufficiently small constant total variation error, versus $\Theta(\rho)$ quantum queries. This matches known $\widetilde O(\rho^4)$ classical upper bounds up to logarithmic factors. Related separations hold for positive-definite systems, least squares, ridge regression, matrix powers and square roots, Hamiltonian evolution, and top-principal-component sampling. The constructions hide $n^2$ unknown signs in fixed-magnitude matrix entries, making classical norm and sampling operations input-independent. Output coordinates encode $n$ Fourier coefficients of those signs. Bounded sine or cosine tests distinguish exact output samples from low-query classical algorithms; conditional-expectation calculations and martingale concentration establish the lower bounds. A transfer theorem extends the argument across tasks. Quantum upper bounds use amplitude amplification or block encodings and QSVT; search reductions establish quantum lower bounds. The results concern worst-case sampling, not scalar estimation or practical runtime advantage. Error thresholds shrink as conditioning approaches one; several extensions require errors of order $t^4$ with $t\le1/64$. The framework does not cover matrix-vector multiplication or relative-Frobenius-error low-rank approximation. Removing the logarithmic loss and establishing joint accuracy dependence remain open.