What is "dequantization" and which quantum claims did it take down?

A quantum advantage claim has two components: a quantum runtime and a classical baseline. Dequantization is what happens when someone finally builds the classical baseline the claim should have been measured against. The quantum algorithm does not break. The math stays correct. The comparison dies — and with it, the word "exponential." This is the single most repeated failure mode of quantum machine learning claims, and it has a precise history: it starts in July 2018 with an 18-year-old undergraduate and a recommendation matrix, and its most recent entry is dated April 2026.

What exactly is dequantization?

A quantum algorithm is dequantized when a classical algorithm is found that solves the same problem, under a comparable input model, with at most polynomially — not exponentially — worse runtime. The term entered common use after Ewin Tang's 2018 result: the Kerenidis–Prakash quantum recommendation algorithm (arXiv:1603.08675, ITCS 2017) ran in time polylogarithmic in the matrix dimensions and was believed exponentially faster than any classical method. Tang produced a classical algorithm running in O(poly(k) · polylog(m,n)) — polylogarithmic in the dimensions too, polynomially slower in the rank k. Exponential separation: gone.

The important nuance, and the reason this is a Pillar C explainer and not an accusation: dequantization is a corrected measurement, not exposed fraud. Kerenidis–Prakash's quantum algorithm was and remains correct; Tang's classical algorithm even reuses their structural insight. What fell was the belief that no fast classical solution existed. Nobody had looked hard enough — until the quantum claim made it worth looking.

How does an exponential speedup collapse? The access-model trick

Every fallen claim in this family died the same way, and the mechanism was flagged in print three years before Tang: Aaronson's "Read the fine print" (Nature Physics, 2015) warned that quantum machine learning speedups leaned on a state-preparation assumption — the algorithm is handed its data pre-loaded as quantum amplitudes, via a QRAM that nobody has built at scale.

Tang's move was to level the bench: give the classical algorithm an analogous power — ℓ²-norm sampling access to the data (the classical shadow of what QRAM grants). Under matched access models, the exponential gap collapsed to polynomial. Her follow-up (arXiv:1811.00414, published in PRL 2021) stated it in the title: quantum PCA "only achieves an exponential speedup because of its state preparation assumptions." That is the whole trick. Not better hardware. Not a new physics result. The same access, granted to both sides.

If this sounds familiar, it should: it is the theory-side twin of why a weak classical baseline ruins a quantum benchmark. A benchmark with an underpowered classical rival, and a theorem with an underpowered classical input model, fail identically — the advantage is created by the comparison, not by the physics.

Which claims fell?

The 2020 framework paper is the systemic one: it showed a single classical sampling technique — ℓ²-norm sampling approximates matrix products in time independent of dimension — dequantizes essentially the entire low-rank QML portfolio in one pass. And the April 2026 entry shows the mechanism is still active outside QML: the short-path algorithms' claimed super-quadratic edge over classical search for MAX-k-CSP-type problems shrinks back toward the ordinary quadratic (Grover-class) regime once the right classical algorithm is written. That last row is a preprint and could still move in either direction; we log it as claimed, not settled.

Which claims are still standing — and why?

Dequantization has a boundary, and it is not arbitrary — parts of it are theorem-shaped:

Read the pattern: everything dequantized so far lived in the low-rank + sampling-access regime. Nothing in the sparse / high-precision regime has fallen — and Gharibian–Le Gall gives the sharpest version of the line: the same QSVT task flips from classically simulable to BQP-complete when the precision requirement tightens from constant to inverse-polynomial. The moat around surviving quantum advantage is not a marketing claim; it is a completeness proof.

How should you read the next "exponential speedup" claim?

Three questions, in order. One: does the classical side get the same data-access model the quantum side assumes? If the quantum algorithm is handed QRAM-loaded states and the classical rival must read raw disk, the comparison is broken by construction — that is the Tang test. Two: is the baseline the best known classical algorithm today, or the best one cited in the paper's related-work section? Those diverge, and the divergence is where benchmarks die. Three: if the claim survives both, ask where the crossover point actually sits — a real asymptotic advantage can still be commercially irrelevant for decades. And keep advantage separate from supremacy: dequantization operates on useful-task claims, which is exactly why it matters for buyers.

Rosetta's own sealed runs (V-0012 and the RQ series) are optimization benchmarks, not QML — we have no proprietary measurement in the dequantization class and do not claim one. What our ledger practice shares with this history is the operating rule it validates: every advantage claim is "not yet" until it survives the strongest classical rival under matched access — because six times in eight years, the rival showed up late and won.

What we don't know

• Whether the surviving polynomial edges matter in practice. Post-dequantization, low-rank QML tasks may retain small polynomial quantum advantages on paper; nobody has measured them end-to-end on real hardware against tuned classical sampling code. No published head-to-head exists.
• Whether QRAM at the assumed scale can be built at all. If it cannot, the original quantum runtimes were hypothetical on both ends of the comparison. As of August 2026 there is no at-scale QRAM demonstration.
• Whether Le Gall–Tamaki is the last word on short-path. It is a preprint (Apr 2026), not yet peer-reviewed; constants on both sides may still move.
• How many currently-standing claims have a dequantization pending. The Quantum Algorithm Zoo lists hundreds of quantum algorithms; no registry tracks the strength of each one's classical baseline over time. That gap is structural — and it is the gap a verification ledger exists to close.
• Rosetta has no sealed runs in this problem class. Our measured data is optimization-class; everything above rests on the cited external literature.

Rosetta Q publishes verdicts with reproducible raw data. This is educational content, not a product claim.