Algorithm Zoo · Machine learning
Tang's Dequantization
Also known as: Quantum-inspired recommendation systems, Classical-quantum equivalent algorithms
First described: Ewin Tang, 2018
The problem
Solve quantum-machine-learning problems classically with poly(log N) sampling instead of full O(N) reads.
Tang's insight: many 'exponential' quantum speedups in ML (Kerenidis-Prakash recommendation systems, low-rank matrix algorithms) assume quantum data access (QRAM). Give classical algorithms the same kind of sample-and-query access and the exponential gap collapses to polynomial.
Best classical
Tang's algorithm itself — was the quantum algorithm before Tang.
Quantum complexity
n/a (this dequantizes quantum algorithms)
Our verdict
The most important result in QML since Lloyd-Mohseni-Rebentrost. Ewin Tang was an 18-year-old undergraduate when she dequantized recommendation systems. Every 'exponential quantum ML speedup' claim should be read with Tang's question in mind: does this assume quantum data access that's unavailable in practice?
When to use it
- When evaluating any claimed quantum ML speedup that assumes QRAM-style data loading.
- As a classical alternative — Tang-style algorithms are sometimes competitive in their own right.
When not to use it
- When the quantum data is *natively* quantum (chemistry, not classical features) — Tang doesn't apply.
Classical baseline
Tang's algorithms achieve poly(log N, 1/ε, κ, rank) complexity matching the quantum versions. The constants are bad in practice but the asymptotic message is clear: assumed quantum advantage needed a quantum data input model that does not exist.
Hardware cost
n/a (classical algorithm)
Key papers
- A quantum-inspired classical algorithm for recommendation systems ↗
Tang · 2019 · STOC
- Quantum-inspired classical algorithms for principal component analysis and supervised clustering ↗
Tang · 2018 · arXiv
Deep-dive tutorials
Last verified: 2026-05-24