The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is Tight
quant-ph, cs.DS, math.OC
Submitted: 2026-10-30
Updated: 2026-10-30
Terminology
Sources
- Forrelation: A Problem that Optimally Separates Quantum from Classical Computing
- Complexity-Theoretic Foundations of Quantum Supremacy Experiments
- Quantum-inspired algorithms in practice
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Quantum Amplitude Amplification and Estimation
- An Improved Classical Singular Value Transformation for Quantum Machine Learning
- The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
- A simple analysis of a quantum-inspired algorithm for solving low-rank linear systems
- Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
- Revisiting dequantization and quantum advantage in learning tasks
- Towards Optimizing the Expected Performance of Sampling-Based Quantum-Inspired Algorithms
- Optimal scaling quantum linear systems solver via discrete adiabatic theorem
- Faster quantum linear system solver beyond the condition number
- Dequantization and Hardness of Spectral Sum Estimation
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
- An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems
- An improved quantum-inspired algorithm for linear regression
- Quantum algorithm for solving linear systems of equations
- Disentangling Hype from Practicality: On Realistically Achieving Quantum Advantage
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements