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 Õ(ρ) queries, whereas the best dequantized algorithms use Õ(ρ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.
Related
- Volume of quasi-homogeneous sublevel sets: Two linear algebra deterministic algorithms with convergence rates
- Randomized algorithms in numerical linear algebra for scientific computing
- Quantum algorithms for optimal control: large-scale finite-horizon linear-quadratic regulation
- Extending structures for the linear framework of Universal Algebra with applications to transposed Poisson algebras
- Linear bounds and sharp exponential growth for commuting matrix algebra
BibTeX
@misc{chakrabarti2026quartic,
title = {{The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight}},
author = {Shouvanik Chakrabarti and Dylan Herman and Junhyung Lyle Kim and Guneykan Ozgul},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.42069},
eprint = {2610.42069},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.42069},
}
RIS
TY - UNPB
TI - The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
AU - Shouvanik Chakrabarti
AU - Dylan Herman
AU - Junhyung Lyle Kim
AU - Guneykan Ozgul
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.42069
UR - https://arxiv.org/abs/2610.42069
AB - 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 Õ(ρ) queries, whereas the best dequantized algorithms use Õ(ρ^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.
ER -