Dequantization & Quantum Kernels
When classical algorithms catch up, and when they cannot.
In 2018 Ewin Tang set out to prove that the quantum recommendation-system algorithm was exponentially faster than every classical algorithm, and instead found a classical algorithm that matches it up to polynomial factors. The moral generalizes: when a quantum speedup comes from the input model, give the classical algorithm the same input model. Quantum kernels face a different enemy, exponential concentration, and survive it only in special cases.
What you’ll learn
- Define sample-and-query access and explain why it is the fair classical analogue of QRAM-based state preparation.
- Prove the length-squared sampling lemma and use it to sketch Tang's dequantized recommendation algorithm.
- State the scope of the dequantization framework and what it cannot touch.
- Derive the exponential concentration of fidelity kernels for random-like embeddings and its shot cost.
- Describe a provable kernel advantage (discrete logarithm) and the geometric-difference test for data.
The input model is the speedup
QML algorithms for classical data typically assume a QRAM loaded with a binary tree of partial sums of squared entries (Kerenidis & Prakash 2017), so that can be prepared in time. The same tree lets a classical computer walk from root to leaf, choosing each child with probability proportional to its stored weight, and so sample with probability in steps. Measuring in the computational basis produces exactly the same distribution. So if the quantum algorithm may use the tree, the classical competitor should be allowed SQ access.
Length-squared sampling
The engine is an idea of Frieze, Kannan and Vempala (1998): sample rows with probability proportional to their squared norms, and rescale.
Draw row indices independently from (possible with SQ access) and rescale each sampled row.
Each sampled outer product is an unbiased estimate of .
The terms are independent, so the variance is at most times one term's second moment; .
Markov's inequality. The sample size does not depend on or at all. The catch: the error is measured against , so it resolves the top- singular values only if is modest. Low (stable) rank is the price of dimension independence.
Tang's algorithm, in outline:
- Length-squared sample rows of , then sample columns of the result, giving a small matrix .
- Compute the top singular vectors of classically, in time independent of and .
- These define approximate right singular vectors of implicitly, as known combinations of the sampled rows.
- The recommendation (row projected onto the top singular space) is a combination of a few such vectors; rejection sampling with SQ access to rows draws an index from its distribution.
Which change to the problem would most clearly put it beyond this kind of dequantization?
- The matrix entries are real rather than complex
- The matrix is sparse, full rank and well conditioned (), as in HHL's hard instances
- The rank parameter doubles
- The user index is chosen at random
Show the answer
B. The matrix is sparse, full rank and well conditioned (), as in HHL's hard instances
Sampling-based algorithms need to be small, which fails for full-rank matrices. Sparse, well-conditioned inversion is BQP-complete, so a classical algorithm for it would imply .
The dequantization framework and its limits
| Task | Input model | Classical with SQ access? |
|---|---|---|
| Recommendation systems (Kerenidis–Prakash) | low rank, QRAM | yes, polynomially slower (Tang 2019) |
| Low-rank linear systems and regression | low rank, QRAM | yes (Chia, Lin & Wang; Gilyén, Lloyd & Tang; Chia et al.) |
| Quantum PCA on classical data | low rank, QRAM | yes (Tang 2021) |
| Sparse, well-conditioned linear systems (HHL) | sparse oracle | no, unless |
| Hamiltonian simulation, factoring | structured | no, unless |
Quantum kernels: power and limits
With embedding , the fidelity kernel is , estimated as the all-zeros probability of . A projected kernel instead compares reduced states of single qubits, (Huang et al. 2021).
A model of a highly expressive embedding, one whose states form an approximate 2-design over the data distribution.
Off-diagonal kernel values cluster at with spread about .
With shots per entry, the all-zeros outcome appears about times.
With a polynomial shot budget almost every off-diagonal estimate is exactly 0. The Gram matrix carries no information about the data, and the trained model only memorizes the training set.
For a random-like 20-qubit embedding, the mean off-diagonal kernel value is . About how many shots per Gram entry (in millions) do you need just to expect one all-zeros outcome?
Show the answer
1.05 million
gives , and resolving the differences between entries, which are also of order , takes many times more. At 50 qubits the budget is hopeless.
For real data, Huang et al. (2021) proposed a test before any claim of advantage: the geometric difference between a classical and a quantum Gram matrix (both normalized to trace ),
If is small, the classical kernel provably predicts about as well as the quantum one for every labeling of those inputs. Only a large , growing like for training points, leaves room for advantage, and then only for some labelings.
Key takeaways
- Sample-and-query access is the classical analogue of QRAM state preparation; the same data structure supports both.
- Length-squared sampling estimates with rows, independent of dimension, and works when is effectively low rank.
- Tang and successors dequantized recommendation systems, low-rank regression, PCA and low-rank QSVT tasks up to polynomial factors; sparse full-rank and BQP-complete problems stay quantum.
- Fidelity kernels with expressive embeddings concentrate at , so polynomial shot budgets yield and no generalization.
- Provable kernel advantages exist for cryptographic problems (discrete log); for real data, tests like the geometric difference should precede any claim.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which classical access model is the fair comparison for QML algorithms that assume QRAM-loaded classical data?
- Query access to individual entries only
- The full matrix in memory, processed by linear-time scans
- An oracle that solves linear systems
- Sample-and-query access: entry queries plus length-squared sampling and norms
Show the answer
D. Sample-and-query access: entry queries plus length-squared sampling and norms
The binary-tree data structure that enables QRAM state preparation also supports classical length-squared sampling in time, so the classical side should get SQ access.
Length-squared sampling approximates to Frobenius error using rows. When does this guarantee recover the top- singular space?
- When is modest, i.e. is effectively low rank
- When is sparse
- When and are small
- When is full rank and well conditioned
Show the answer
A. When is modest, i.e. is effectively low rank
The error must be small compared with , which needs . That is affordable exactly when the Frobenius mass is concentrated in a few singular values.
A 30-qubit fidelity kernel uses an embedding that behaves like a random state. You estimate each Gram entry with 10,000 shots. What do you typically see off the diagonal?
- Values near 1/2, with statistical error about 0.005
- Values near 1, because states crowd together in high dimension
- Almost always exactly 0: the expected number of all-zeros outcomes is about
- Accurate values near with 1% relative error
Show the answer
C. Almost always exactly 0: the expected number of all-zeros outcomes is about
Random states in dimension are nearly orthogonal: . With shots you almost never observe a single all-zeros outcome, so .
The Liu–Arunachalam–Temme kernel advantage rests on which assumption, and what hardware does it need?
- Hardness of SAT; noisy near-term devices
- Classical hardness of the discrete logarithm; fault-tolerant Shor-type circuits
- No assumption, since it is unconditional; any quantum device
- Hardness of the permanent; photonic hardware
Show the answer
B. Classical hardness of the discrete logarithm; fault-tolerant Shor-type circuits
The labels are defined through discrete logarithms, which the quantum feature map effectively computes with Shor-type circuits. The classical lower bound assumes the discrete logarithm is classically hard.
Further reading
- E. Tang, "A quantum-inspired classical algorithm for recommendation systems", Proc. STOC (2019); arXiv:1807.04271.
- N.-H. Chia, A. Gilyén, T. Li, H.-H. Lin, E. Tang & C. Wang, "Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning", Proc. STOC (2020).
- Y. Liu, S. Arunachalam & K. Temme, "A rigorous and robust quantum speed-up in supervised machine learning", Nature Physics 17, 1013 (2021).
- H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven & J. R. McClean, "Power of data in quantum machine learning", Nat. Commun. 12, 2631 (2021).
- S. Thanasilp, S. Wang, M. Cerezo & Z. Holmes, "Exponential concentration in quantum kernel methods", Nat. Commun. (2024).