Dequantization

In July 2018 an 18-year-old undergraduate at UT Austin named Ewin Tang posted a paper on arXiv that broke the quantum-machine-learning community's favourite example. The paper was titled A quantum-inspired classical algorithm for recommendation systems. Tang had taken a 2016 quantum algorithm by Iordanis Kerenidis and Anupam Prakash — a widely-celebrated construction that recommended products to users exponentially faster than any known classical method — and had written a classical algorithm whose running time matched it term-for-term. The quantum advantage, Tang showed, had never been exponential. It had been hidden in the fine print of how the algorithm was allowed to read its input.

The paper exploded the field. Scott Aaronson — who had suggested the problem to Tang as a "safe" example of quantum advantage — wrote a widely-read blog post saying that Tang's result was a genuine breakthrough, that it had forced everyone in quantum machine learning to re-examine their claims, and that an entire research programme had been opened overnight. Within two years there were a dozen dequantization papers covering principal-component analysis, linear systems, supervised learning, and beyond.

This chapter is about what dequantization is, what it does to the map of quantum speedups, and how it changes the way a careful reader should evaluate claims of the form "our quantum algorithm solves problem X exponentially faster than any classical algorithm."

The setup — where quantum speedups are claimed

To see what dequantization attacks, first look at where the strong speedup claims actually live. A clean taxonomy of quantum algorithms by speedup strength:

Row 2 — the fragile row — is the one this chapter is about. All of those algorithms make the same implicit bargain: "give the quantum computer a magical input-loading procedure (QRAM), and I will show you an exponential speedup." The dequantization programme asks a quiet, devastating question: what happens if you give the classical computer a matched loading procedure? Do you still get exponential speedup, or does the gap vanish?

The answer, for much of row 2, is that the gap vanishes.

Sampling access — the idea that dequantizes everything

The key concept is the sampling-access model. Classical algorithms usually assume an input matrix A \in \mathbb{R}^{m \times n} is stored in memory as an array of mn numbers. Just to read the matrix is O(mn) work. Under this model, any algorithm that produces an output dependent on all of A costs at least O(mn).

But what if the algorithm can do something gentler? What if, instead of reading every entry, it can:

1. Query any entry A_{ij} in O(\text{polylog}(mn)) time.
2. Sample a row index i with probability proportional to the row's squared norm: \Pr[i] \propto \|A_i\|^2.
3. Given a row i, sample a column j with probability proportional to |A_{ij}|^2.

This is called \ell_2-sampling access, sometimes written as SQ(A) for "sampling and query access." It is a specific, mild strengthening of plain array access — and it is realistic: a preprocessed database of user preferences can be stored in a data structure (a tree of norms) that supports exactly these operations in logarithmic time per operation.

Why does this model matter? Because QRAM — the quantum-random-access memory that HHL, quantum PCA, and quantum recommendation systems all assume — provides the quantum equivalent of sampling access. QRAM lets a quantum circuit load a state \sum_i \sqrt{p_i}\,|i\rangle\,|A_i\rangle in time polylogarithmic in mn, where p_i \propto \|A_i\|^2. That is, in Dirac notation, the amplitudes are already the square-roots of the sampling probabilities.

Why this connection is lethal for exponential-speedup claims: if the quantum algorithm's speed comes from loading data in polylogarithmic time via QRAM, the speedup is really coming from QRAM, not from quantum mechanics per se. And a classical algorithm with matched sampling access can do the equivalent loading classically in polylogarithmic time. So the comparison that ought to be made is not "quantum-with-QRAM vs classical-with-full-read" (rigged) but "quantum-with-QRAM vs classical-with-sampling-access" (fair).

Tang's argument — dequantizing recommendation systems

Here is Tang's 2018 result in the shortest honest form. A recommendation system has m users and n products, with a preference matrix A \in \mathbb{R}^{m \times n} that is low-rank (the true preferences are explained by a small number k of latent factors). You want to recommend a product to user i: that is, you want a sample from a distribution proportional to the entries of the i-th row of a good low-rank approximation A_k to A.

The Kerenidis-Prakash quantum algorithm (2016) did this in time O(\text{poly}(k, \log(mn), 1/\varepsilon)). The speed came from: (1) QRAM loading the matrix, (2) quantum singular-value projection to isolate the top-k singular components, (3) measuring the resulting state to sample a recommendation.

Tang's classical algorithm does the same in the same asymptotic time. The ingredients:

1. Length-squared sampling to estimate inner products. If you have SQ(A) — sampling access to a matrix A — you can estimate \langle v, A_i \rangle for any vector v stored in memory in time O(\|v\|^2 \|A_i\|^2 / (\varepsilon^2 \|\langle v, A_i\rangle\|^2)). This is a classical statistical statement: sampling entries with probability \propto |A_{ij}|^2 gives an unbiased estimator of the inner product, and a few samples concentrate by Chebyshev.

2. Low-rank matrix approximation via sampling. Frieze, Kannan, and Vempala (1998!) showed that a good rank-k approximation of A can be built from a small number of sampled rows — polynomial in k and 1/\varepsilon, independent of m and n. This is the foundation of "importance sampling for linear algebra." Tang extended it with sampling access.

3. Sampling from the top-k projection. Given an approximate A_k, sample entries of its i-th row using the data structure. This is the recommendation.

The total running time is O(\text{poly}(k, \log(mn), 1/\varepsilon)) — polylogarithmic in mn, polynomial in k and 1/\varepsilon. Exactly the same scaling as the quantum algorithm. The quantum advantage, it turned out, had never been exponential: it had been an artefact of comparing a QRAM-enabled quantum algorithm to a plain-access classical one.

Hype check. "Quantum algorithm X is exponentially faster than any classical algorithm" should always be read as "quantum algorithm X is exponentially faster than any classical algorithm I happened to check." Before 2018 nobody had checked whether sampling-access classical algorithms could match Kerenidis-Prakash. The moment Tang did, the exponential gap vanished. This is the dequantization reader's reflex: which classical input model is the quantum speedup being compared to, and is that the fair comparison?

What got dequantized in the years that followed

Tang's paper set off a chain reaction. Here is a timeline of the headline dequantizations.

The most important technical paper is CGLLT 2020 — arXiv:1910.06151 — Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. It does for QML what Shor's algorithm did for factoring: it gives a single unified technique that dequantizes a whole family of problems at once. The headline result: for any quantum algorithm that uses QRAM + quantum singular-value transformation on a matrix with stable rank \tilde{r} = \|A\|_F^2 / \|A\|^2, there is a classical sampling-access algorithm with running time polynomial in \tilde{r}, \log(mn), and 1/\varepsilon. Low stable rank — and most QML-relevant matrices do have low stable rank — is where the dequantization bites.

What survives dequantization

The dequantization programme has not eaten quantum computing. Several classes of problems have provable reasons to resist it.

Shor's factoring algorithm

Factoring an integer N reduces to finding the period of the function f(x) = a^x \bmod N — an instance of the hidden-subgroup problem on the cyclic group \mathbb{Z}_N. Shor's algorithm solves it in time polynomial in \log N. The best known classical algorithm (the general number field sieve) takes time sub-exponential but super-polynomial — roughly \exp(O((\log N)^{1/3})) — and no sampling-access trick has ever produced a classical polynomial-time factoring algorithm. The hidden-subgroup structure is fundamentally different from the low-rank matrix structure dequantization exploits: there is no "row-norm distribution" to sample from, because the function is defined on an abelian group and the hard object is a phase relationship, not a matrix entry.

Grover's search — provably not dequantized

For unstructured search of an N-element database, the BBBV lower bound (Bennett, Bernstein, Brassard, Vazirani, 1997 — see quantum-query-lower-bounds) proves that no quantum algorithm can do better than \Omega(\sqrt{N}) queries to the oracle. Grover's algorithm achieves O(\sqrt{N}), so it is optimal. Classically, the problem requires \Omega(N) queries — also a matching bound. The gap between N and \sqrt{N} is quadratic, not exponential, and it is tight on both sides. No sampling-access trick can break the classical \Omega(N) lower bound, because the oracle offers no structure to sample against.

Hamiltonian simulation of generic local Hamiltonians

Simulating the time evolution e^{-iHt} of an n-qubit system whose Hamiltonian H is a sum of geometrically local terms is a problem quantum computers can solve in time polynomial in n and t (Lloyd 1996, Berry-Childs, Low-Chuang). Classical algorithms for the same problem have to store or propagate the 2^n-dimensional state vector: exponential in n in the worst case. Tensor-network methods can handle low-entanglement states efficiently, but the worst-case Hamiltonian-simulation problem is QMA-hard — there is no sampling access that reduces it. This is the clean exponential quantum advantage that survives all dequantization attempts.

Amplitude estimation

Estimating the amplitude a = \langle 0 | U^\dagger P U | 0 \rangle of a quantum circuit U to additive accuracy \varepsilon takes O(1/\varepsilon) quantum queries — a quadratic Monte Carlo speedup over the classical O(1/\varepsilon^2) required by sampling. The quadratic is provably optimal (lower bound by BBBV-style reasoning) and the problem does not fit the sampling-access framework. Amplitude estimation is the reason Grover-like quadratic speedups survive in many downstream applications — amplitude-amplified Monte Carlo is a real, undequantizable speedup.

When dequantization bites HHL

The HHL algorithm for linear systems Ax = b is the poster child for both the best and the worst of dequantization. The quantum algorithm runs in time polynomial in \log n, \kappa (condition number), s (sparsity), and 1/\varepsilon — an exponential-in-n speedup over any direct classical solver that reads A.

But: does HHL survive dequantization? The answer is it depends on the matrix.

• Sparse, well-conditioned, high-rank matrices: HHL is not currently dequantized. These are the matrices that come from, for instance, discretised partial differential equations. The quantum speedup is believed to be real.
• Low-rank or low-stable-rank matrices: CGLLT 2020 proved that, given sampling access to A and b, a classical algorithm matches HHL in \tilde{O}(\text{poly}(\tilde{r}, \kappa, \log n, 1/\varepsilon)). The stable-rank case is the most common case in machine learning — any time your features are low-dimensional after preprocessing — and it is precisely the case where HHL gets dequantized.
• Cryptographic-scale linear systems (e.g. from lattice cryptography): different problem, different structure, not the HHL regime.

The practical upshot for a reader evaluating a QML or HHL application: ask what the input matrix looks like. If the claim is "our quantum algorithm solves problem X exponentially faster than any classical algorithm, on data that has low rank after preprocessing," the claim is almost certainly dequantizable. If the claim is "our quantum algorithm solves problem X exponentially faster than any classical algorithm, on sparse operators that arise from physics simulation," the claim might be robust.

Worked examples

The implications for quantum machine learning

Dequantization changed the way the QML literature is read. Before 2018, papers routinely claimed "exponential speedup over classical" without specifying the classical access model. After 2018, a responsible paper must either:

1. Show that the quantum algorithm outperforms classical sampling-access algorithms too, or
2. Work in a regime where sampling access is unavailable (e.g. inputs generated at runtime, not pre-stored), or
3. Prove a dequantization-resistant structure (e.g. the matrix has high stable rank).

Many pre-2018 QML claims have been re-evaluated. Some survive (HHL on specific sparse-structured PDE matrices; variational quantum algorithms on problems with no classical-sampling analogue; quantum simulation). Many do not (quantum PCA on feature matrices; quantum recommendations; supervised kernel methods where the kernel is a classically-computable inner product).

The field has converged on a sharper, more honest position: quantum machine learning is an open research question, not a solved speedup story. Variational algorithms on NISQ hardware might offer advantages for problems classical machine learning cannot efficiently address — but the advantage, if it exists, is not the old "exponentially faster linear algebra" advantage. That one is gone.

Common confusions

"Dequantization means quantum computing is useless"

No. Dequantization narrows the set of problems where quantum advantage is exponential; it does not eliminate the set. Shor's, Grover's, Hamiltonian simulation, amplitude estimation, and various cryptographic primitives all survive. Dequantization disciplines the claims, it does not refute the field.

"Dequantization shows classical beats quantum"

Not in any general sense. Dequantization shows classical matches quantum in certain sampling-access settings — the two scale identically, both polynomial in the relevant parameters. The gap that was claimed (exponential) is revealed to be an artefact of the comparison; the gap that remains (constant factors, practical overhead, the difficulty of building a big QRAM) could go either way in practice.

"Tang's result killed QML"

QML in its 2016 form — exponential-speedup claims for kernel methods and linear algebra — has been substantially weakened. But modern QML (variational quantum eigensolvers for chemistry, quantum reservoir computing, generative quantum models, quantum kernel methods evaluated on honestly-hard-to-compute kernels) is a live field with open questions. The researcher's task is harder, not impossible.

"If a problem admits sampling access, quantum has no advantage"

Too strong. Sampling access dequantizes low-rank or low-stable-rank problems. For high-rank or high-condition-number problems, the classical sampling algorithms get expensive (polynomial in the stable rank, which for a high-rank matrix is essentially as bad as reading the whole matrix). Quantum advantage can still exist in those regimes.

"Dequantization means QRAM is worthless"

QRAM is still the input model that justifies HHL and related algorithms on sparse, high-rank, well-conditioned matrices — the regime where they are not dequantized. What dequantization showed is that QRAM is not magic: once you grant classical algorithms matched access, matched speedups follow for matched-structure inputs.

The India angle

Indian quantum-algorithms groups — at TIFR Mumbai, IISc Bangalore, IIT Madras, and CMI Chennai — have followed and contributed to the dequantization literature. Sanjeev Arora and Satyen Kale (Indian-born theoretical computer scientists at Princeton and Google) wrote foundational papers on matrix multiplicative-weights methods that underpin modern classical sampling algorithms; these techniques feed into dequantization proofs. Indian PhD theses on quantum complexity routinely engage with the dequantization frame when evaluating quantum-advantage claims for QML.

The broader Indian QML community — QpiAI, TCS Research, Infosys quantum, and the NQM-funded algorithm research at IIT Madras — treats dequantization seriously in internal evaluations: before claiming a quantum speedup for an industrial problem, the default check is "does CGLLT apply?" Only claims that pass that check are published as exponential-speedup claims.

Going deeper

The CGLLT framework in precise terms

CGLLT 2020 — Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning — proves the following master theorem. Let A \in \mathbb{R}^{m \times n} be a matrix with SQ(A) access, stable rank \tilde r = \|A\|_F^2 / \|A\|^2, and condition number \kappa. For any polynomial p of degree d, there is a classical algorithm that, given SQ(A) access and a vector b with SQ(b) access, outputs SQ(p(A)\,b) up to accuracy \varepsilon in time

The \tilde r^{11} is ugly but polynomial; the polylog in mn is the key feature. This covers singular-value projection (polynomial approximation of projectors), matrix inversion (polynomial approximation of 1/x on the relevant spectral band — see HHL), and most QML linear-algebra primitives. The result is: any quantum algorithm built on QRAM + QSVT on a low-stable-rank matrix has a matching classical algorithm in the sampling-access model.

The proof technique is a combination of FKV-style low-rank sampling, Monte Carlo polynomial evaluation, and careful concentration inequalities. It is entirely classical — no quantum reasoning appears anywhere in the proof. The mechanical transformation of quantum linear-algebra claims into classical sampling-access claims is now well-understood.

Sampling access vs block-encoding

Modern quantum algorithms are often phrased in terms of block-encoding: a unitary U such that A / \alpha appears in the top-left block of U for some normalisation \alpha \geq \|A\|. Block-encoding subsumes QRAM and is the input model for quantum singular-value transformation.

The dequantization analogue of block-encoding is SQ(A) plus the ability to sample according to the singular-value distribution. CGLLT proved that, for matrices of stable rank \tilde r, these two classical access models are interchangeable up to polynomial overhead. This is the technical underpinning of the equivalence between quantum block-encoding advantages and classical sampling-access advantages in the low-stable-rank regime.

Known limits of dequantization

Some problems provably resist sampling-access dequantization:

• Quantum Fourier sampling over non-abelian groups: the dihedral hidden subgroup problem, which is connected to lattice cryptography.
• Simulation of highly-entangled quantum dynamics: matrix product states can simulate low-entanglement states but fail for volume-law-entangled states.
• Sampling problems from BosonSampling and IQP: these circuits are provably hard classically under plausible complexity-theoretic assumptions.
• Certain cryptographic tasks: BB84-based QKD, quantum money, position-verification — these exploit no-cloning, not speedup.

The current research frontier is: for which classes of machine-learning problems can we prove quantum-advantage lower bounds, dequantization-proof? As of 2025, the honest answer is "few and narrow," which is itself a sobering result for QML's long-term prospects.

Classical-quantum stable-rank dichotomy

A crisp way to think about what dequantization found: there is a stable-rank dichotomy. Let \tilde r(A) be the stable rank of the input.

• Low \tilde r (small number of effective components): classical sampling beats or matches quantum. Dequantized.
• High \tilde r (matrix is "fully dimensional"): the \tilde r^{11} factor in CGLLT becomes prohibitive; quantum can retain polynomial-in-\log(mn) scaling where classical cannot. Quantum advantage possible.

Most pre-2018 QML papers studied low-\tilde r inputs, because those are the ones where the quantum algorithm's claimed speedup was cleanest to state. Exactly the regime dequantization was designed to eat.

The open questions

Three questions the dequantization programme has not fully answered:

1. Is there an HHL regime that is provably not dequantized and also arises in natural applications? Sparse PDE matrices are the candidate; the speedup is widely believed but not provably dequantization-resistant.
2. Can quantum neural networks — variational circuits with parameters learned by gradient descent — provide advantages dequantization does not cover? The answer depends on whether the parameter landscape has classical simulability under some sampling model; recent results on barren plateaus suggest structure in the landscape that classical algorithms might exploit.
3. What is the right complexity class for QML problems? BQP-vs-P for sampling access is the natural frame, but the answer is wide open.

The intellectual virtue dequantization teaches

Beyond the technical content, dequantization is a lesson in epistemic humility for the quantum-algorithms community. The right question is not "my algorithm is exponentially faster — can anyone prove otherwise?" The right question is "my algorithm uses these classical resources — have I fairly compared against a classical algorithm with matched resources?" Tang's 2018 paper made that question unavoidable. Every quantum-advantage claim since has had to answer it.

Where this leads next

With dequantization understood, the next natural step is error mitigation — the NISQ-era bridge techniques that let variational quantum algorithms extract signal from noisy hardware even when the underlying algorithm does not have a provable exponential advantage. Together, dequantization and error mitigation form the honest contemporary view: quantum computing is a real field with a real set of advantages, but the advantages are narrower and harder-won than the press-release version suggests.

The related chapters lessons about quantum speedups, HHL algorithm, and quantum kernels fill in adjacent pieces of this map.

References

1. Ewin Tang, A quantum-inspired classical algorithm for recommendation systems (2018) — arXiv:1807.04271.
2. Ewin Tang, Quantum-inspired classical algorithms for principal component analysis and supervised clustering (2018) — arXiv:1811.00414.
3. Chia, Gilyén, Li, Lin, Tang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning (2020) — arXiv:1910.06151.
4. John Preskill, Lecture Notes on Quantum Computation, Chapter 7 — theory.caltech.edu/~preskill/ph229.
5. Wikipedia, Quantum-inspired algorithm.
6. Scott Aaronson, How much structure is needed for huge quantum speedups? — arXiv:2209.06930.