Simple Algorithm
Quantum Computing · Rydberg State · 30 min

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 ∣Ai,⋅⟩\ket{A_{i,\cdot}} can be prepared in poly⁡log⁡(mn)\poly\log(mn) 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 ii with probability ∣vi∣2/∥v∥2\abs{v_i}^2/\norm{\mathbf v}^2 in O(log⁡n)\order{\log n} steps. Measuring ∣v⟩\ket{\mathbf v} 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.

DerivationUnbiased, with dimension-free variance
  1. pi=∥Ai,⋅∥2∥A∥F2,S=(Ai1,⋅/rpi1⋮Air,⋅/rpir)∈Cr×np_i=\frac{\norm{A_{i,\cdot}}^2}{\norm A_F^2},\qquad S=\begin{pmatrix}A_{i_1,\cdot}/\sqrt{rp_{i_1}}\\\vdots\\A_{i_r,\cdot}/\sqrt{rp_{i_r}}\end{pmatrix}\in\C^{r\times n}

    Draw rr row indices independently from pp (possible with SQ access) and rescale each sampled row.

  2. E[S†S]=∑t=1r∑ipi Ai,⋅†Ai,⋅rpi=A†A\mathbb E\big[S^\dagger S\big]=\sum_{t=1}^{r}\sum_ip_i\,\frac{A_{i,\cdot}^\dagger A_{i,\cdot}}{rp_i}=A^\dagger A

    Each sampled outer product is an unbiased estimate of A†A/rA^\dagger A/r.

  3. E ∥S†S−A†A∥F2≤r∑ipi ∥Ai,⋅∥4r2pi2=1r∑i∥Ai,⋅∥2∥A∥F2=∥A∥F4r\mathbb E\,\norm{S^\dagger S-A^\dagger A}_F^2\le r\sum_ip_i\,\frac{\norm{A_{i,\cdot}}^4}{r^2p_i^2}=\frac1r\sum_i\norm{A_{i,\cdot}}^2\norm A_F^2=\frac{\norm A_F^4}{r}

    The rr terms are independent, so the variance is at most rr times one term's second moment; ∥Ai,⋅†Ai,⋅∥F=∥Ai,⋅∥2\norm{A_{i,\cdot}^\dagger A_{i,\cdot}}_F=\norm{A_{i,\cdot}}^2.

  4. r≥1ε2δ ⇒ Pr⁡[∥S†S−A†A∥F≥ε∥A∥F2]≤δr\ge\frac{1}{\varepsilon^2\delta}\ \Rightarrow\ \Pr\Big[\norm{S^\dagger S-A^\dagger A}_F\ge\varepsilon\norm A_F^2\Big]\le\delta

    Markov's inequality. The sample size does not depend on mm or nn at all. The catch: the error is measured against ∥A∥F2\norm A_F^2, so it resolves the top-kk singular values only if ∥A∥F2/σk2\norm A_F^2/\sigma_k^2 is modest. Low (stable) rank is the price of dimension independence.

Tang's algorithm, in outline:

  1. Length-squared sample rr rows of AA, then sample cc columns of the result, giving a small r×cr\times c matrix WW.
  2. Compute the top singular vectors of WW classically, in time independent of mm and nn.
  3. These define approximate right singular vectors of AA implicitly, as known combinations of the sampled rows.
  4. The recommendation (row ii 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 ℓ2\ell_2 distribution.
Check your understanding

Which change to the problem would most clearly put it beyond this kind of dequantization?

  1. The matrix entries are real rather than complex
  2. The matrix is sparse, full rank and well conditioned (κ=poly⁡log⁡N\kappa=\poly\log N), as in HHL's hard instances
  3. The rank parameter kk doubles
  4. The user index ii is chosen at random
Show the answer

B. The matrix is sparse, full rank and well conditioned (κ=poly⁡log⁡N\kappa=\poly\log N), as in HHL's hard instances

Sampling-based algorithms need ∥A∥F2/σ2\norm A_F^2/\sigma^2 to be small, which fails for full-rank matrices. Sparse, well-conditioned inversion is BQP-complete, so a classical poly⁡log⁡N\poly\log N algorithm for it would imply BPP=BQP\mathsf{BPP}=\mathsf{BQP}.

The dequantization framework and its limits

TaskInput modelClassical with SQ access?
Recommendation systems (Kerenidis–Prakash)low rank, QRAMyes, polynomially slower (Tang 2019)
Low-rank linear systems and regressionlow rank, QRAMyes (Chia, Lin & Wang; Gilyén, Lloyd & Tang; Chia et al.)
Quantum PCA on classical datalow rank, QRAMyes (Tang 2021)
Sparse, well-conditioned linear systems (HHL)sparse oracleno, unless BPP=BQP\mathsf{BPP}=\mathsf{BQP}
Hamiltonian simulation, factoringstructuredno, unless BPP=BQP\mathsf{BPP}=\mathsf{BQP}
Dequantization targets the low-rank regime, where the exponential speedup came from the data structure. It cannot touch BQP-complete problems.

Quantum kernels: power and limits

With embedding ρ(x)=U(x)∣0n⟩ ⁣⟨0n∣U(x)†\rho(\mathbf x)=U(\mathbf x)\dyad{0^n}U(\mathbf x)^\dagger, the fidelity kernel is k(x,x′)=Tr⁡[ρ(x)ρ(x′)]k(\mathbf x,\mathbf x')=\Tr[\rho(\mathbf x)\rho(\mathbf x')], estimated as the all-zeros probability of U(x′)†U(x)U(\mathbf x')^\dagger U(\mathbf x). A projected kernel instead compares reduced states of single qubits, kPQ(x,x′)=exp⁡(−γ∑q∥ρq(x)−ρq(x′)∥F2)k^{\mathrm{PQ}}(\mathbf x,\mathbf x')=\exp\big(-\gamma\sum_q\norm{\rho_q(\mathbf x)-\rho_q(\mathbf x')}_F^2\big) (Huang et al. 2021).

DerivationConcentration for random-like embeddings
  1. ∣ϕ(x)⟩, ∣ϕ(x′)⟩ independent Haar-random in d=2n ⇒ k=∣⟨ϕ(x)∣ϕ(x′)⟩∣2∼Beta(1, d−1)\ket{\phi(\mathbf x)},\ \ket{\phi(\mathbf x')}\ \text{independent Haar-random in } d=2^n\ \Rightarrow\ k=\abs{\braket{\phi(\mathbf x)|\phi(\mathbf x')}}^2\sim\mathrm{Beta}(1,\,d-1)

    A model of a highly expressive embedding, one whose states form an approximate 2-design over the data distribution.

  2. E[k]=1d,Var⁡[k]=d−1d2(d+1)≈1d2\mathbb E[k]=\frac1d,\qquad\operatorname{Var}[k]=\frac{d-1}{d^2(d+1)}\approx\frac{1}{d^2}

    Off-diagonal kernel values cluster at 2−n2^{-n} with spread about 2−n2^{-n}.

  3. E[#{0n}]=S k≈S⋅2−n\mathbb E\big[\#\{0^n\}\big]=S\,k\approx S\cdot2^{-n}

    With SS shots per entry, the all-zeros outcome appears about S2−nS2^{-n} times.

  4. S=poly⁡(n)≪2n ⇒ K^≈IS=\poly(n)\ll2^n\ \Rightarrow\ \hat K\approx\id

    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.

Predict before you look

For a random-like 20-qubit embedding, the mean off-diagonal kernel value is 2−202^{-20}. 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

S⋅2−20=1S\cdot2^{-20}=1 gives S=220≈1.05×106S=2^{20}\approx1.05\times10^6, and resolving the differences between entries, which are also of order 2−202^{-20}, 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 mm),

g(KC∥KQ)=∥KQ (KC)−1KQ∥∞.g(K^{\mathrm C}\Vert K^{\mathrm Q})=\sqrt{\norm{\sqrt{K^{\mathrm Q}}\,(K^{\mathrm C})^{-1}\sqrt{K^{\mathrm Q}}}_\infty}.

If gg is small, the classical kernel provably predicts about as well as the quantum one for every labeling of those inputs. Only a large gg, growing like m\sqrt m for mm 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 A†AA^\dagger A with O(1/ε2)\order{1/\varepsilon^2} rows, independent of dimension, and works when AA 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 2−n2^{-n}, so polynomial shot budgets yield K^≈I\hat K\approx\id 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.

Question 1

Which classical access model is the fair comparison for QML algorithms that assume QRAM-loaded classical data?

  1. Query access to individual entries only
  2. The full matrix in memory, processed by linear-time scans
  3. An oracle that solves linear systems
  4. 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 O(log⁡n)\order{\log n} time, so the classical side should get SQ access.

Question 2

Length-squared sampling approximates A†AA^\dagger A to Frobenius error ε∥A∥F2\varepsilon\norm A_F^2 using O(1/ε2)\order{1/\varepsilon^2} rows. When does this guarantee recover the top-kk singular space?

  1. When ∥A∥F2/σk2\norm A_F^2/\sigma_k^2 is modest, i.e. AA is effectively low rank
  2. When AA is sparse
  3. When mm and nn are small
  4. When AA is full rank and well conditioned
Show the answer

A. When ∥A∥F2/σk2\norm A_F^2/\sigma_k^2 is modest, i.e. AA is effectively low rank

The error ε∥A∥F2\varepsilon\norm A_F^2 must be small compared with σk2\sigma_k^2, which needs ε≲σk2/∥A∥F2\varepsilon\lesssim\sigma_k^2/\norm A_F^2. That is affordable exactly when the Frobenius mass is concentrated in a few singular values.

Question 3

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?

  1. Values near 1/2, with statistical error about 0.005
  2. Values near 1, because states crowd together in high dimension
  3. Almost always exactly 0: the expected number of all-zeros outcomes is about 104⋅2−30≈10−510^4\cdot2^{-30}\approx10^{-5}
  4. Accurate values near 2−302^{-30} with 1% relative error
Show the answer

C. Almost always exactly 0: the expected number of all-zeros outcomes is about 104⋅2−30≈10−510^4\cdot2^{-30}\approx10^{-5}

Random states in dimension 2302^{30} are nearly orthogonal: k≈2−30k\approx2^{-30}. With 10410^4 shots you almost never observe a single all-zeros outcome, so K^≈I\hat K\approx\id.

Question 4

The Liu–Arunachalam–Temme kernel advantage rests on which assumption, and what hardware does it need?

  1. Hardness of SAT; noisy near-term devices
  2. Classical hardness of the discrete logarithm; fault-tolerant Shor-type circuits
  3. No assumption, since it is unconditional; any quantum device
  4. 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).