Metraipolis › archive › dc_2802ff201574

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight — arXiv:2610.42069

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.42069
License (as archived): CC0-1.0
Archived: 2026-11-03T08:16:36.781Z
SHA-256 of the archived text: 200829dbf3dabae234c7043c0e81e9d0512b35ec114b3833e892a01e4a916815
Stable URL of this page: https://metraipolis.com/documento/dc_2802ff201574

How to cite

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight — arXiv:2610.42069 — arXiv (en), https://arxiv.org/abs/2610.42069 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2802ff201574 (Metraipolis archive dc_2802ff201574, sha256 200829dbf3dabae234c7043c0e81e9d0512b35ec114b3833e892a01e4a916815)

BibTeX

@misc{dc2802ff201574,
  title = {The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight — arXiv:2610.42069},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42069},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2802ff201574; sha256 200829dbf3dabae234c7043c0e81e9d0512b35ec114b3833e892a01e4a916815},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42069. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.42069 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T08:04:23.917Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).