Quantum algorithms for linear algebra typically access a matrix $A$ via quantum random access memory (QRAM) and prepare quantum states proportional to the solutions of linear systems. The corresponding dequantized classical algorithms, given sampling and query access to $A$, return sampling and query access to an approximate solution. Both families of algorithms use a number of queries that is polynomial in the normalized Frobenius norm $\rho=\|A\|_F/\|A\|$ and does not depend directly on the dimension.\
For linear systems with fixed condition number $\kappa$ and accuracy, quantum algorithms require $\widetilde O(\rho)$ queries, whereas the best known dequantized algorithms need $\widetilde O(\rho^4)$. We prove that this quartic gap is tight in the worst case up to a logarithmic factor. Specifically, for any constant $\kappa_0>1$ we construct dense linear systems with condition number at most $\kappa_0$ such that sampling from the solution within a sufficiently small total variation distance demands $\Omega(\rho^4/\log\rho)$ classical queries but only $\Theta(\rho)$ quantum queries.\
The same separation holds 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, provided the error thresholds are small enough. Consequently, many quantum linear‑algebra algorithms achieve a near‑quartic speedup over classical algorithms with sampling and query access in the worst case. All these classical lower bounds stem from a unified framework based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.\
Review: The paper establishes, via constructive lower bounds, that the quartic quantum‑classical speedup for linear‑algebra tasks cannot be further improved, solidifying the theoretical limits of quantum advantage.