EUVIMEDEUVIMED entdecken
Crossref

Quantum Time-Space Tradeoffs for Matrix Problems

Paul Beame, Niels Kornerup, Michael Whitmeyer

SIAM Journal on Computing · 30.06.2026 · 55 (3) · 469-519

DOI: 10.1137/24m1710164 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 20.05.2026. Verfasst von Paul Beame und 2 weiteren Autor:innen. Die Arbeit nennt 46 Literaturangaben. Gefördert von: National Science Foundation, Schmidt Sciences, Sandia National Laboratories.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices [Formula: see text], including the discrete Fourier transform matrix, we prove that quantum circuits with at most [Formula: see text] input queries and [Formula: see text] qubits of memory require [Formula: see text] to compute matrix-vector product [Formula: see text] for [Formula: see text]. We similarly prove that matrix multiplication for [Formula: see text] binary matrices requires [Formula: see text]. Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e., AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for [Formula: see text] Boolean matrix multiplication to [Formula: see text] from [Formula: see text]. Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits.

Förderung

  • National Science Foundation
  • Schmidt Sciences
  • Sandia National Laboratories
  • Simons Foundation

Zitieren

APA

Beame, P., Kornerup, N., & Whitmeyer, M. (2026). Quantum Time-Space Tradeoffs for Matrix Problems. SIAM Journal on Computing, 55(3), 469-519. https://doi.org/10.1137/24m1710164

Vancouver

Beame P, Kornerup N, Whitmeyer M. Quantum Time-Space Tradeoffs for Matrix Problems. SIAM Journal on Computing. 2026;55(3):469-519. doi:10.1137/24m1710164

BibTeX
@article{Beame2026,
  author = {Beame, Paul and Kornerup, Niels and Whitmeyer, Michael},
  title = {Quantum Time-Space Tradeoffs for Matrix Problems},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {3},
  pages = {469--519},
  doi = {10.1137/24m1710164}
}
Kostenlos starten →