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 $\rho=\|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(\rho)$ queries, whereas the best dequantized algorithms use $\widetilde O(\rho^4)$. We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant $\kappa_0>1$, we construct dense linear systems with condition number at most $\kappa_0$ for which sampling from the solution within a sufficiently small constant total variation distance requires $\Omega(\rho^4/\log\rho)$ classical queries but only $\Theta(\rho)$ 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.

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

arXiv:2610.42069 [quant-ph]

(or arXiv:2610.42069v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.42069 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.