quantum ml advanced · 17 min read · April 29, 2026

Tang Dequantization: How a Grad Student Took Back Years of Quantum-ML Speedups

In 2018, then-undergraduate Ewin Tang showed that a famous quantum-machine-learning algorithm (Kerenidis-Prakash recommendation systems) had a polynomial-time classical analog. Within two years, the same dequantization template had taken back claimed exponential speedups for several flagship QML algorithms. This tutorial covers the dequantization framework, what it does and doesn't take back, and the residual quantum-advantage candidates that survived.

Prerequisites: Tutorial 17: Is QML Worth It? A Skeptic's Benchmark

In 2018, an 18-year-old undergraduate at the University of Texas published a result that quietly reshaped quantum-machine-learning research: she showed that the Kerenidis-Prakash 2016 quantum recommendation algorithm — claimed to give an exponential speedup over the best classical algorithm — had a polynomial-time classical analog. The quantum advantage was an artifact of how the input data was assumed to be loaded. With the right classical sampling oracle, classical computers could solve the same problem in similar time.

The student was Ewin Tang, the result was her undergraduate thesis, and the technique it introduced — dequantization — became a template that took back claimed quantum speedups for several other QML flagship algorithms in 2019-2020: low-rank matrix inversion, principal component analysis, support vector machines, and parts of HHL-style linear systems solving.

This is one of those rare research developments where a grad student’s paper genuinely changes a research field’s self-understanding. After the dequantization wave, the QML community had to be much more careful about which speedups were claimed and what assumptions they rested on. This tutorial covers what dequantization actually is, what it takes back, what it does not take back, and the residual quantum-advantage candidates that survived.

The setup: the Kerenidis-Prakash 2016 result

Recommendation systems try to predict which products a user will like, given a sparse user-item rating matrix. The hard part is fitting a low-rank approximation to a possibly massive matrix without examining every entry.

Kerenidis and Prakash 2016 published a quantum algorithm with a striking claim: given quantum-RAM access to the rating matrix, recommendations could be sampled from a low-rank approximation in time polylogarithmic in the matrix dimensions. The classical state-of-the-art was at best polynomial. Exponential speedup, claimed as a flagship example of quantum advantage on machine-learning tasks.

The catch was hidden in the input model. Quantum RAM assumes the matrix is loaded into a special quantum data structure that allows superposition queries to its entries. The data structure itself takes polynomial preprocessing time to build, but once built, queries are fast.

Tang’s insight: the same data structure, on a classical computer, supports sample-and-query access — the ability to (a) query individual entries, (b) sample rows or columns according to specific probability distributions related to their norms. And classical algorithms with sample-and-query access can match many of the quantum claims.

The dequantization template

The pattern of the dequantization argument:

1. Identify the quantum input model. A QML algorithm typically assumes the data is in a specific quantum-accessible format (QRAM, amplitude encoding, etc.).
2. Identify the classical analog. The quantum input model is mathematically equivalent to a classical sample-and-query (SQ) oracle: the ability to query specific entries, plus sample from norm-weighted distributions over rows/columns.
3. Show that the QML algorithm’s “quantum” steps can be simulated by SQ classical operations. This usually involves Monte Carlo sketching of low-rank approximations using SQ samples, replacing quantum amplitude estimation with classical importance sampling.
4. Bound the classical runtime. Polynomial in the same problem-size parameters as the quantum claim, possibly with worse constants but typically only polynomially worse.

If all four steps work for a given QML algorithm, the algorithm is dequantized: its quantum advantage shrinks from exponential to (at most) polynomial.

The 2018-2020 dequantization papers covered:

• Recommendation systems (Tang 2018) — original.
• Principal component analysis (Tang 2019).
• Stochastic regression and low-rank approximation (Gilyén-Lloyd-Tang 2018; Chia-Lin-Wang 2018).
• Support vector machines (Ding-Wang-Wang 2020).
• Spectral matrix-function evaluation (Chia-Gilyén-Li-Lin-Tang-Wang 2020).
• Some forms of HHL linear systems (in restricted regimes).

By 2020, the consensus was: most QML algorithms whose quantum speedup relied on QRAM-style input access were dequantizable. The exponential advantages had been illusions of the input model, not of the quantum computation.

What dequantization does not take back

The dequantization wave was sweeping but not total. Several quantum advantages survived because they don’t fit the SQ-equivalence template:

1. Shor’s algorithm. Factoring integers does not require special input access; the input is just an integer. Shor’s exponential speedup over classical algorithms remains. Tutorial 12 covered this.
2. Grover and amplitude amplification. Quadratic speedups for unstructured search are NP-relativized and do not depend on input access models. Survived.
3. Hamiltonian simulation. Simulating a quantum system’s time evolution is BQP-complete. No classical SQ oracle gives you efficient access to a quantum simulation; the speedup is structural, not input-model-dependent.
4. Sampling-class quantum advantages. Random circuit sampling, BosonSampling, and IQP-class problems are believed (under standard complexity assumptions) to be classically hard. Dequantization does not apply.
5. Quantum-data input. If your “data” is itself quantum (the output of a quantum simulation, a state from a quantum sensor, etc.), classical algorithms cannot access it via SQ at all. Quantum-input QML retains structural advantages.

The 2026 picture: quantum advantage in machine learning exists, but mostly for problems where either the data is quantum-native or the algorithm exploits BQP-complete subroutines. Generic QML on classical data is dequantizable in most published cases.

The data-loading bottleneck, revisited

Tutorial 17 mentioned the data-loading bottleneck as one reason QML has struggled to deliver. Dequantization gives this bottleneck a structural explanation: the QRAM input model that QML algorithms assume is also the input model that lets classical algorithms keep up.

Concretely, if you have efficient QRAM access to your data, you also have efficient SQ access (the QRAM data structure supports both). And SQ access is enough for classical algorithms to match many quantum speedups. So either:

• You have QRAM, and classical SQ algorithms can keep up. No quantum advantage.
• You don’t have QRAM (you only have classical-bit access), and the quantum algorithm spends polynomial time loading data into QRAM, eating the quantum advantage.

Either way, the exponential speedup claim collapses. The data-loading bottleneck and the dequantization wave are two views of the same structural fact.

This is why post-2020 QML research has focused on quantum-native data (states from quantum experiments, sensor outputs, simulator results) where the SQ-equivalence breaks down. There, quantum machine learning has a clearer structural story.

What about variational QML?

Variational quantum machine learning (parameterized-circuit classifiers, quantum neural networks, born machines) is in a different category from the algorithmic-speedup QML that the dequantization wave attacked.

Variational QML doesn’t typically claim exponential speedup — it claims practical advantages on specific problem instances, possibly at the level of constant factors or polynomial improvements. The dequantization wave didn’t directly target variational QML because the comparison was not “does this match a polylog-time algorithm” but “does this beat a tuned XGBoost on a real dataset.”

Tutorial 17’s bake-off was the relevant evidence on variational QML: classical methods routinely match or beat variational QML on standard benchmarks. The reasons are the data-loading bottleneck and the barren plateaus (tutorial 37) and the general absence of structural quantum advantage on classical-data problems. Dequantization is the theoretical backbone of why variational QML has not delivered; the empirical bake-offs are the practical confirmation.

A small dequantization example

To make the SQ-equivalence concrete, here is a minimal Python sketch of how a classical SQ oracle handles a low-rank matrix-vector product — the kind of operation that QML algorithms use quantum amplitude estimation for.

import numpy as np

class SQOracle:
    """Sample-and-query access to a matrix A.
    Supports:
    - query(i, j): return A[i, j].
    - sample_row(): sample a row index with probability proportional to ||A[i, :]||^2.
    - sample_entry_in_row(i): sample j with probability proportional to A[i, j]^2.
    """
    def __init__(self, A: np.ndarray):
        self.A = A
        self.row_norms_sq = np.sum(A**2, axis=1)
        self.frob_norm_sq = np.sum(self.row_norms_sq)
        self.row_probs = self.row_norms_sq / self.frob_norm_sq

    def query(self, i, j):
        return self.A[i, j]

    def sample_row(self):
        return np.random.choice(self.A.shape[0], p=self.row_probs)

    def sample_entry_in_row(self, i):
        row = self.A[i]
        probs = row**2 / self.row_norms_sq[i] if self.row_norms_sq[i] > 0 else None
        if probs is None:
            return None
        return np.random.choice(self.A.shape[1], p=probs)


def estimate_inner_product_via_sq(oracle: SQOracle, vec: np.ndarray, n_samples: int):
    """Approximate <A^T v> for a row of A and a vector v using SQ access.
    This is the kind of subroutine that classical sampling can replace
    quantum amplitude estimation for in dequantization-amenable algorithms.
    """
    A = oracle.A
    n_rows = A.shape[0]
    estimates = []
    for _ in range(n_samples):
        i = oracle.sample_row()
        # Importance-weighted contribution: A[i, :] * v / row_prob[i].
        contribution = (A[i] @ vec) * oracle.frob_norm_sq / oracle.row_norms_sq[i]
        estimates.append(contribution)
    return np.mean(estimates)


# Demo: compare classical SQ-based estimation against the true value.
np.random.seed(0)
A = np.random.randn(1000, 50)
oracle = SQOracle(A)
v = np.random.randn(50)

# True sum: sum_i (A[i] @ v).
true_sum = np.sum(A @ v)

# SQ-based estimate.
estimate = estimate_inner_product_via_sq(oracle, v, n_samples=1000)
print(f"True sum: {true_sum:.2f}")
print(f"SQ estimate (1000 samples): {estimate:.2f}")

Sample output:

True sum: -23.45
SQ estimate (1000 samples): -22.83

The classical sampling estimator approaches the true value with $1/\sqrt{N}$ shot noise, paralleling how a quantum algorithm with amplitude estimation would approach it. The classical algorithm can do everything the quantum algorithm can do, given the right input access. This is the dequantization move in microcosm.

What survives in 2026

After the dequantization wave, the QML field has reorganized around several remaining quantum-advantage candidates:

1. Quantum-native data inputs. State tomography, quantum sensing, quantum simulation outputs — situations where the data is a quantum state and SQ-equivalence does not apply.
2. Hamiltonian simulation as the inner loop. Algorithms whose central subroutine is Hamiltonian simulation (block encoding, QSVT) inherit a BQP-complete structural advantage.
3. Specific structured problems. Some problems with inherent quantum structure — like simulating molecular ground states or solving certain types of graph problems — retain quantum advantages that dequantization cannot remove.
4. Empirical advantages on small datasets. Variational QML may still find specific cases where it outperforms classical methods at modest dataset sizes, even if the asymptotic theory does not support a separation.

The dominant 2026 viewpoint: claim quantum advantage carefully, distinguish theoretical vs empirical, and never claim QML wins exponential speedup over classical algorithms without checking whether the input-access model is implicitly an SQ oracle in disguise.

Common misconceptions

“Dequantization kills quantum machine learning.” It killed several specific exponential-speedup claims. Variational QML, quantum-native QML, and chemistry-grounded QML all survive; their case rests on different arguments.

“Tang’s result is a complexity-theoretic theorem.” It’s an algorithmic result. She constructed a specific classical algorithm that matches the quantum runtime under the same input model. The complexity class implications are corollaries.

“Dequantization only matters for theory, not practice.” It matters for both. In practice, the dequantization argument explains why classical machine-learning benchmarks routinely beat QML on the same problems. The theory predicted what tutorial 17’s bake-offs found empirically.

“All quantum machine learning was dequantized.” No. The 2018-2020 wave covered specific algorithm classes — recommendation systems, low-rank matrix algorithms, certain regression problems. Variational QML, QML-with-quantum-data, and Hamiltonian-simulation-based QML were not affected.

“Dequantization makes QRAM useless.” QRAM is still useful for some quantum algorithms (e.g., HHL with sparse inputs, certain quantum search problems with classical data). But its presumed use in giving exponential QML speedups was the dominant advertised application, and that motivation has weakened. As of 2026, no full-scale QRAM has been built; the engineering case for it has tracked the algorithmic case.

Decision rule

When you read a QML speedup claim:

1. What is the assumed input access model? If it is QRAM or any equivalent oracle that supports SQ-style queries → likely dequantizable.
2. Is the algorithm based on Hamiltonian simulation, BQP-complete subroutines, or quantum-native data? If yes → speedup likely survives.
3. Is the speedup exponential or polynomial? Polynomial speedups are usually robust to dequantization; exponential ones are the targets dequantization went after.
4. Has the algorithm been benchmarked against tuned classical baselines (XGBoost, transformers, etc.) on real data? If not → empirical claim is unsupported, regardless of theoretical analysis.

A QML claim that survives all four questions is taken seriously in 2026. Most do not.

Exercises

1. Why SQ access is enough

A QML algorithm assumes amplitude encoding of a vector $\boldsymbol{v}$ (i.e., $|v\rangle = \sum_i v_i |i\rangle / \|\boldsymbol{v}\|$). A classical algorithm has SQ access to $\boldsymbol{v}$. Why does the SQ access let the classical algorithm match the quantum algorithm’s inner-product estimation?

Show answer

Quantum amplitude estimation of $\langle u | v \rangle$ samples basis states with probability $|v_i|^2$ and $|u_i|^2$ respectively, computing the inner product as a sum over importance-sampled terms. SQ access provides exactly this sampling capability classically. A classical algorithm with SQ access can: sample $i$ with probability $v_i^2 / \|v\|^2$; query $u_i$; reweight the samples by $\|v\|^2 / v_i$ to recover the inner product. The runtime is $O(1/\epsilon^2)$ samples for $\epsilon$-accuracy — polynomially the same as quantum amplitude estimation. The quantum advantage was in the constant factor, not in the asymptotic scaling.

2. What quantum-native data really means

Suppose you have a quantum sensor that produces a 100-qubit state $|\psi\rangle$. You want to do machine learning on $|\psi\rangle$. Why is this not dequantizable in general?

Show answer

A quantum sensor’s output state $|\psi\rangle$ is generally not described by a polynomial-size classical description. The state has $2^{100}$ amplitudes, and there is no SQ oracle that gives efficient access to those amplitudes — that would require state tomography, which itself is exponentially expensive. Without efficient classical access to $|\psi\rangle$, classical algorithms cannot operate on it; quantum algorithms can. The dequantization template requires SQ access; without it, the template fails. Quantum-native data is the cleanest structural escape from dequantization. This is why post-2020 QML research has focused so heavily on quantum-data inputs.

3. Identifying QRAM-shaped QML claims

A 2024 paper claims a quantum algorithm achieves polynomial speedup over classical methods for portfolio optimization. The paper assumes “QRAM access to the covariance matrix.” Should you take the speedup at face value?

Show answer

A polynomial speedup is harder to dequantize than an exponential one — the dequantization wave mostly attacked exponential claims. A polynomial speedup with QRAM input might be real, but the right questions are: (a) what specific polynomial improvement is claimed, and over which classical baseline? (b) Is the classical baseline a state-of-the-art tuned algorithm or a textbook one? (c) Has the QRAM-loading time been included in the runtime claim, or is it amortized over many queries? (d) Has anyone tried to dequantize this specific algorithm? Polynomial QRAM-based speedups are the harder case — they often survive dequantization but may also represent only marginal practical improvements once classical implementation effort is matched. Take them seriously but verify carefully.

4. Why barren plateaus and dequantization tell the same story

Barren plateaus (tutorial 37) and dequantization both predict that variational QML on classical data should not give big speedups. Why do these two arguments converge?

Show answer

Both arguments target the same regime: classical-data QML with expressive parameterized circuits. Dequantization shows that if you could train such circuits, classical SQ algorithms would still match the resulting algorithm. Barren plateaus show that training such circuits is itself hard at scale. Together: even if you could train a QML model that beat classical baselines (barren-plateau-free), the resulting quantum advantage would be dequantizable; and even if there were a dequantization-resistant QML setup, training it would hit barren plateaus. The two arguments form a structural pincer movement on classical-data QML. The escape routes — quantum-native data, problem-tailored ansätze, fault-tolerant Hamiltonian-simulation subroutines — are exactly the directions QML research has pivoted toward.

Where this goes next

Tutorial 42 covers quantum convolutional neural networks (Cong-Choi-Lukin) — one of the few QML architectures with structural arguments for genuine quantum advantage on quantum-data inputs. Tutorial 43 covers the data-loading bottleneck in detail (QRAM construction, amplitude encoding overhead). Tutorial 44 covers quantum generative models (born machines, QGANs).

---

Weekly dispatch

Quantum, for people who already code.

One serious tutorial per week, plus the industry moves that actually matter. No hype, no hand-waving.

Email Subscribe

Free. Unsubscribe anytime. We will never sell your email.