The Honest Scorecard

Start with the cautionary tale, because it is the one most often left out. Around 2016 a celebrated result — the Kerenidis–Prakash quantum recommendation-system algorithm — claimed an exponential speedup: given sparse ratings data structured as a low-rank matrix, a quantum computer could suggest a good product in time polynomial in the log of the matrix dimensions, where the known classical methods ran in time polynomial in the dimensions themselves. It was one of the flagship examples of “quantum machine learning,” a whole family of algorithms built on quantum linear algebra — solving linear systems (HHL), principal component analysis, support-vector machines — all promising exponential gains on low-rank problems.

In 2018, an eighteen-year-old undergraduate named Ewin Tang was handed the recommendation problem as a challenge to prove a matching classical lower bound — to show it could not be done classically. She proved the opposite. By importing the quantum algorithm's own assumption — fast, structured ${\ell }^2$-norm sampling access to the data — into a classical algorithm, she matched the quantum runtime up to polynomial factors. The exponential speedup was an illusion: it had been measured against a classical algorithm denied the same data-access model, not the best one. This is dequantization.

What followed was a cascade. The same “quantum-inspired” sampling technique dequantized much of low-rank linear-algebra QML: regression, PCA, supervised clustering, the low-rank cases of the matrix problems that had anchored the field. The polynomial exponents were often large — these classical algorithms are not necessarily fast — but the exponential separation was gone. The lesson is not that quantum computing failed; it is a rule of evidence, and it is the rule this entire book has followed:

where the second term means the best classical algorithm that exists, granted every resource the quantum one is granted — not the textbook default that happens to be easy to beat. A speedup measured against a strawman is not a speedup.

If low-rank linear-algebra QML dequantizes, where does a durable learning advantage live? The clearest answer of the last few years is: where the data itself is quantum. Every algorithm in Part IV so far assumed classical inputs — feature vectors, images, ratings — that had to be loaded into amplitudes, and it is exactly that loading, that classical description, which lets a classical algorithm sample its way to the same answer. Take the classical description away.

Suppose the data are physical quantum states ${\rho }_1,{\rho }_2,\dots$ — the outputs of a quantum sensor, a chemistry experiment, or another quantum device — handed to the learner coherently, without ever being measured into a classical list. A learner that can hold several copies at once and entangle them before measuring can extract properties that any learner restricted to single-copy measurements provably cannot, with an exponential gap in the number of samples required. Huang, Kueng, Preskill and collaborators (2021–2022) proved separations of exactly this shape, and demonstrated some on real hardware. The intuition is clean: measurement is the lossy keyhole of Chapter 1, and if your data are born quantum, forcing them through that keyhole one copy at a time throws away information that a coherent quantum memory keeps.

This is a narrower promise than the early hype — it needs quantum-native data, not spreadsheets — but it is a firmer one, because there is no classical description to sample from in the first place. It sits beside Hamiltonian simulation (Chapter 9) as an advantage grounded in the physics rather than in an accounting trick. Keep the distinction sharp: quantum data, plausibly yes; classical data dressed in amplitudes, usually dequantizable. The tool that explains why is next.

Here is the unifying idea, and it reaches all the way back to Chapter 3. An $n$-qubit amplitude vector has $2^n$ entries, but most physically relevant states do not use that space fully — they are only lightly entangled. A matrix product state (MPS) is the data structure that cashes low entanglement into low cost. It rewrites each amplitude as a product of small matrices, one per site:

where each $A_{s_k}^{[k]}$ is a $\chi \times \chi$ matrix selected by the physical bit $s_k\in \{0,1\}$ (the boundary matrices are row and column vectors, so the product lands on a number). The internal indices contracted between neighbours are the bond indices, and their size $\chi$ — the bond dimension — is the one number that controls everything. Store the chain and the cost is

When $\chi$ is small this is a colossal saving, and the schematic below shows why it is possible at all: the physical legs carry the qubits, and the horizontal bonds carry the correlations between one side of a cut and the other.

Now the exact link to Chapter 3. Cut the chain between sites $m-1$ and $m$ and write the Schmidt decomposition across that bipartition,

the very object of Chapter 3. The number of nonzero Schmidt coefficients is the Schmidt rank, and the bond dimension the MPS needs on that cut is exactly that rank. A product state has Schmidt rank 1 everywhere, so $\chi =1$ suffices; a Bell or GHZ state has rank 2, so $\chi =2$ suffices; a maximally entangled cut of a half-chain needs the full $\chi =2^{n/2}$, and the saving evaporates. The entanglement entropy makes the bound quantitative. Since $S=-{\sum }_i{\lambda }_i^2{\log }_2{\lambda }_i^2$ is the Shannon entropy of a distribution on $\chi$ outcomes, it can be at most ${\log }_2\chi$, so

A state whose entanglement entropy across every cut is bounded by a constant (an area law, typical of ground states of local, gapped Hamiltonians) needs only a constant $\chi$ — it is classically tractable. This is the engine behind the density-matrix renormalization group and the classical simulation of a great deal of quantum many-body physics. And it is the boundary of quantum advantage stated as a theorem: if a quantum circuit keeps its entanglement low — bounded $\chi$ throughout — then a tensor network tracks it in polynomial time, and whatever that circuit was doing is dequantized. A variational quantum model that never leaves the low-entanglement regime cannot be beating a classical one; a genuine quantum advantage must spend entanglement the network cannot afford. Turn the knob and watch the price:

The slider tells the whole story in one gesture. At small $\chi$ the MPS is cheap but wrong — it has thrown away Schmidt components the state actually carries — and the fidelity sits well below 1. Raise $\chi$ and the discarded components return, the fidelity climbs monotonically, and at $\chi =\text{rank}$ the reconstruction is exact. Low entanglement, cheap; high entanglement, expensive; and never a free lunch in between.

The lab builds an MPS engine from scratch and checks it against a from-scratch full state-vector simulator (the workhorse of Chapter 2, rebuilt here with real amplitudes so a real SVD suffices). The construction is the canonical left-to-right sweep: reshape the state into a matrix at each bond, take its singular value decomposition, keep the largest $\chi$ singular values, and carry the remainder forward. The truncation — the one place fidelity can be lost — is a single call:

1/// Truncated SVD of `m`: keep the `chi_max` largest singular values (and, if
2/// `tol > 0`, drop any singular value below `tol · σ_max` as numerically zero).
3/// Returns (U_k [rows×k], σ_k [k], Vᵀ_k [k×cols]) with σ sorted descending.
4fn trunc_svd(m: &DMatrix<f64>, chi_max: usize, tol: f64) -> (DMatrix<f64>, Vec<f64>, DMatrix<f64>) {
5    let svd = m.clone().svd(true, true);
6    let u = svd.u.expect("U");
7    let vt = svd.v_t.expect("Vt");
8    let s = svd.singular_values;
9    let p = s.len();
10
11    // defensively sort by singular value, descending
12    let mut idx: Vec<usize> = (0..p).collect();
13    idx.sort_by(|&a, &b| s[b].partial_cmp(&s[a]).unwrap());
14
15    let smax = if p > 0 { s[idx[0]] } else { 0.0 };
16    let keep_by_tol = if tol > 0.0 {
17        idx.iter().filter(|&&i| s[i] > tol * smax).count().max(1)
18    } else {
19        p
20    };
21    let k = chi_max.min(keep_by_tol).max(1).min(p);
22    // … assemble U_k, σ_k, Vᵀ_k from the top-k columns/rows …
23}

The sweep threads that truncation down the chain — even the reshape is an explicit loop, so no library is trusted with the index bookkeeping. Each site's $U$ factor becomes a left-canonical tensor (an isometry, so the norm is preserved), the leftover $\sigma V^{\mathsf{T}}$ is pushed into the next site, and the kept singular values are recorded per bond — the referees will demand they are the Schmidt coefficients. The number kept is the new bond dimension:

1for _s in 0..n {
2        let ncol = carry.ncols();
3        let cols_next = ncol / d;
4        // reshape (chi_left × ncol) → M (chi_left·d × cols_next)
5        let mut mmat = DMatrix::<f64>::zeros(chi_left * d, cols_next);
6        for a in 0..chi_left {
7            for phys in 0..d {
8                for rest in 0..cols_next {
9                    mmat[(a * d + phys, rest)] = carry[(a, phys * cols_next + rest)];
10                }
11            }
12        }
13        let (uk, sk, vtk) = trunc_svd(&mmat, chi_max, tol);
14        let k = sk.len();
15        tensors.push(MpsTensor { l: chi_left, r: k, mat: uk });
16        bond_sigmas.push(sk.clone());
17
18        // carry = diag(σ) · Vᵀ  → (k × cols_next)
19        let mut newcarry = vtk;
20        for row in 0..k {
21            for cc in 0..cols_next {
22                newcarry[(row, cc)] *= sk[row];
23            }
24        }
25        carry = newcarry;
26        chi_left = k;
27    }

To check the MPS against the state vector we contract the whole train back into $2^n$ amplitudes, one site at a time — the bond index $a$ shared by two neighbours is summed over, exactly the matrix product of (17.2):

1/// Contract the MPS back into a full 2^n state vector.
2fn mps_to_vec(tensors: &[MpsTensor], n: usize) -> Vec<f64> {
3    let d = 2usize;
4    let mut acc = tensors[0].mat.clone(); // (2 × r0), phys = 2
5    for s in 1..n {
6        let ts = &tensors[s];
7        let ls = ts.l;
8        let rs = ts.r;
9        let phys = acc.nrows();
10        let mut newacc = DMatrix::<f64>::zeros(phys * d, rs);
11        for pp in 0..phys {
12            for p in 0..d {
13                for b in 0..rs {
14                    let mut sum = 0.0;
15                    for a in 0..ls {
16                        sum += acc[(pp, a)] * ts.mat[(a * d + p, b)];
17                    }
18                    newacc[(pp * d + p, b)] = sum;
19                }
20            }
21        }
22        acc = newacc;
23    }
24    (0..acc.nrows()).map(|i| acc[(i, 0)]).collect()
25}

Eight referees run and write their verdicts to the JSON the panel below reads live — nothing is hardcoded. At a sufficient bond dimension $\chi =2^{\lfloor n/2\rfloor }$ the MPS reproduces the state-vector amplitudes to better than the $4\times 10^{-15}$ tolerance; the untruncated bond dimension equals the Schmidt rank on every cut, not just the centre one (product at $\chi =1$; Bell, GHZ and the 1D cluster state at $\chi =2$, and demonstrably not exact at $\chi =1$); the truncation error of the headline state is monotone non-increasing in $\chi$ and vanishes at full $\chi$; the left-canonical form keeps its isometries and unit norm; and the singular values the sweep keeps are the Schmidt coefficients of the matching cut, value by value. The last three referees grade the headline claim itself. The headline state — a three-layer brickwork circuit whose centre cut is crossed by only one entangler per layer — is reconstructed exactly at $\chi =\text{rank}$, and that rank sits strictly below the generic $2^{\lfloor n/2\rfloor }$ (the compression is real, not a restatement of “exact at full $\chi$”); one bond fewer still loses real weight (the rank is not padded); and the $\chi =1$ truncations land on their analytic closed forms — $F=1/2$ for Bell and GHZ, $F=2^{-(n-1)}$ for the cluster chain.

Run it yourself with cargo run --release in Rust-QML/ch17-tensor. The fidelity curve is the dequantization moral in one picture: a low-entanglement state sits at the cheap left end where a classical tensor network keeps up for free, and only genuinely high-entanglement states force the bond dimension — and the cost — to grow.

Put it all on one table. Across seventeen chapters the evidence sorts into five honest columns, and the scorecard panel above renders them live from the lab. The proven wins are the claims that come with an actual lower bound against the classical side: Grover (Chapter 8) — real and provably optimal, but only quadratic, and only in the oracle model — and learning from quantum data, on the strength of provable sample-complexity separations. One column over sit the believed giants: Shor's period finding (Chapter 7) and Hamiltonian simulation (Chapter 9). No classical rival is known for either, and the speedups are almost certainly real — but this chapter's own equation (17.1) demands the best classical algorithm, and no theorem rules out a classical surprise: there is no classical lower bound for factoring, and none for simulating generic local dynamics. Believed, not proven, is the honest word.

The plausible column holds quantum kernels and feature maps on classical data: advantage exists for carefully engineered, classically hard kernels, but case by case, with no blanket guarantee. And the hard truths sit in the last two columns. Low-rank linear-algebra QML is dequantized — the speedup was against a strawman. Generic NISQ variational QML is open: no proof of advantage, barren plateaus flattening the gradients as the model widens (Chapter 16), and the tensor-network result of this chapter waiting to dequantize any circuit that stays low-entanglement. That is not pessimism; it is the map you need to do useful work.

And so the book closes where it began — with a promise kept. We started with one qubit: two amplitudes, a direction on a sphere, one bit at readout. We grew it into a multi-qubit simulator, priced entanglement as a resource, modelled real noise, built the algorithms that made the field famous and measured exactly what each one buys, kept fragile quanta alive with codes and thresholds, and finally rebuilt learning itself in Hilbert space — feature maps, quantum kernels, variational circuits, and the plateaus that fight back. Every step obeyed the same discipline: propose the formalism, build it in Rust, and hand it to a merciless referee that checks against an exact result — and, just as often, against the best classical rival. You now own that method, and you own the honest scorecard it produces. The exponential is real; so are its limits. Knowing the difference — being able to compute it, referee it, and compare it honestly — is the whole of what this book had to give.