Quantum time-space tradeoffs for matrix problems

DOI10.1137/24M1710164MaRDI QIDQ7262227zbMATH OpenFDO

Authors Paul Beame, Niels Kornerup

Publication date 11 June 2026

Published in SIAM Journal on Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1137/24M1710164

zbMATH Keywords

lower boundsquantum query complexitytime-space tradeoffs

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A general Sequential Time-Space Tradeoff for Finding Unique Elements
• A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs
• A nondeterministic space-time tradeoff for linear codes
• A quantum-inspired classical algorithm for recommendation systems
• A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
• An improved classical singular value transformation for quantum machine learning
• Cumulative memory lower bounds for randomized and quantum computation
• Generalized String Matching
• How to record quantum queries, and applications to quantum indifferentiability
• scientific article; zbMATH DE number 5899238 (Why is no real title available?)
• scientific article; zbMATH DE number 5899240 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 7765405 (Why is no real title available?)
• Limitations of Quantum Advice and One-Way Communication
• On finding quantum multi-collisions
• On the Power of Quantum Computation
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
• Quantum Complexity Theory
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum time-space tradeoff for finding multiple collision pairs
• Rapid solution of problems by quantum computation
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Space efficient algorithms for some graph theoretical problems
• Space-time trade-offs on the FFT algorithm
• Strong direct product theorems for quantum communication and query complexity
• The computational complexity of universal hashing
• The NISQ complexity of collision finding
• Time-space trade-off lower bounds for randomized computation of decision problems
• Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions
• Time-space tradeoffs for algebraic problems on general sequential machines
• Time-space tradeoffs for branching programs
• Time-space tradeoffs for computing functions, using connectivity properties of their circuits
• Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer

This page was built for publication: Quantum time-space tradeoffs for matrix problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7262227)