From Coins to Error Correction · Quantum Computing Column — No. 049: Sampling, Quantum Walks, and the Jiuzhang Machines
> Prerequisite navigation: You need 009 (how quantum advantage is verified), 005 (the exponential-parallelism misunderstanding), 016 (measurement statistics), 034 (lineage of algorithms). > Next episode preview: 050, *Fifty Chapters: A Midterm Review — The Algorithm Capability Map*.
In the corner of a toy store sits a century-old toy: the Galton board. A handful of beads drops in from the top, bounces off staggered rows of pegs, and piles up into a bell-shaped hill at the bottom. This toy doesn't "compute" anything — it simply lets the laws of physics roll the dice, and you count the beads.
The protagonist of this article is a special class of quantum machines with the same temperament as the peg board: no logical operations, no answers — they only physically roll out some probability distribution, and you count the samples. The jargon is *sampling tasks*, and the machines are called *special-purpose quantum machines*. The Jiuzhang series is the most famous Chinese representative (see our article Jiuzhang 4.0, which this piece complements). The other protagonist, the *quantum walk*, is its close cousin on a chessboard. Their shared question is: "The advantage is real — now what?"
Sampling tasks: judged by distribution, not right or wrong
First, the task structure. In the world of general-purpose algorithms, answers are right or wrong. In the world of sampling tasks, the output is a batch of "samples drawn from some distribution" — the criterion isn't "is it correct" but "is the distribution correct": run it ten thousand times, count the frequency of each outcome, and reconcile it against the theoretical distribution (this is exactly what the advantage-verification in chapter 009 does).
The special-purpose machine's philosophy: pick a physical process that is "classically very hard to simulate, yet quantum-mechanically natural," and build it directly. The most famous is the Jiuzhang photonic route: dozens of photons pass through a large interferometric network (a maze woven from beam splitters and phase shifters), and the distribution of photon arrival positions at the outputs — for a classical computer to predict it, it must brute-force an exponentially large interference ledger (the cross-term mobilization of chapter 016); while the quantum machine computes nothing at all — the laws of physics finish the computation for it. The beads fall by themselves; the ledger interferes by itself.
The superconducting route of the Zuchongzhi machines is the circuit version of the same idea: random deep circuits, random measurements — throwing classical simulators an exponentially hard bill. Different routes, same philosophy: physicalize the "hardness," and let nature roll the dice in person.
A tug-of-war: advantage is not a settled verdict
Sampling advantage is most easily misread as "a one-shot verdict," but the real script is a tug-of-war:
- Every time the quantum side releases a new machine or a larger experiment, the classical side's simulation algorithms (the clever tricks of the tensor-network family) follow up with a round: squeezing memory, pruning branches, exploiting structure — scales once deemed "impossible to simulate" get pushed to the edge by classical algorithms within a few years;
- The quantum side then scales up again, and the classical side closes in again — since 2020 this front has swung back and forth over many rounds (as of a Nov 2026 viewpoint), and no "advantage" has ever been declared final.
- Disanalogy one: the peg board's bell-shaped hill is a chaotic certainty (the classical spreading of conserved probability); the quantum sampling machine's distribution is a masterpiece of interference — each landing point's probability is determined by the cross-terms of the entire network (chapter 016), and that's exactly where the "hard to compute" lies. Anyone can predict the peg board; the quantum distribution costs exponential effort to predict.
- Disanalogy two: the peg board's verification is the naked eye (the bell curve); quantum sampling's verification is statistical reconciliation plus a race against classical simulators — a "correct" distribution is not enough; you must also outpace your rival's computation. The verification of sampling advantage is therefore always dynamic (the structural cause of the tug-of-war).
The correct reading: sampling advantage is "scientific evidence," not an "engineering verdict" — its value lies in proving that the line "quantum machines genuinely outrun classical ones on some task" truly exists (the "proof" difficulty of chapter 009 cashes in here), while the exact position of that line drifts with both sides' technologies. What our Jiuzhang 4.0 article records is precisely the latest round of this tug-of-war.
Quantum walks: the cousin on the chessboard
The other protagonist is quieter: the quantum walk. In the classical world, a wandering piece on a graph is a random walk; the quantum "piece" carries amplitudes as it moves — at every fork, the piece splits, all paths proceed in parallel, and interfere with each other at downstream junctions. The result: the quantum piece's "spreading speed" is on the order of twice the classical one (a quadratic improvement in graph-covering efficiency); more astonishingly, mathematicians have constructed special oracle graphs on which quantum walks are exponentially faster than any classical walk (a descendant of the amplitude-amplification family — another member of chapter 034's lineage).
Quantum walks also often appear as sampling machines: the question is not "which path is shortest" but "where has the piece's distribution drifted." They share with the Jiuzhang machines the same awkwardness and the same hope — the task form sits one translation layer away from "real-world needs."
The "so what" question
The most common criticism of special-purpose sampling machines deserves a direct answer. Their three real current values:
One, boundary detector (scientific value, the hardest). In the pre-error-correction era, when deep circuits are unavailable, sampling tasks are the only battlefield where "quantum surpassing classical" can actually be demonstrated — they are shallow (no error correction needed), wide (many qubits are fine), and decidable (distribution testing). As physical evidence that "quantum advantage really exists," they are irreplaceable.
Two, potential applications (honestly: "candidates"). Certain sampled distributions connect to real problems (molecular vibrational spectra, some properties of graph structures, certifiable random numbers — chapter 029's Bell certification comes in handy), but most of these connections remain "possibly useful" arguments, with no industrial deployment yet.
Three, route investment (strategic value). These dedicated routes — photonics, random circuits — push hardware limits (photon counts, gate fidelities) up round by round — accumulating technology and supply chains for the future universal machine.
One-line positioning: special-purpose machines are the advantage vanguard of the NISQ era; universal machines are the long-term king's road — calculators and computers have played out this story once before in history.
Taking the analogy apart
What the peg-board analogy borrows — and doesn't:
Luggage to take home
1. Sampling = letting physics roll the dice: special-purpose machines physicalize "classically hard-to-simulate distributions" directly (photonic interferometric networks / random circuits), verified by statistical reconciliation — Jiuzhang and Zuchongzhi are two hardware incarnations. 2. Advantage is a tug-of-war, not a verdict: classical simulation algorithms close in each round while the quantum side upgrades each round — sampling advantage is dynamic evidence that "the boundary really exists"; quantum walks are its close cousin (quadratic spreading speed, exponential on special constructions). 3. Three answers to "so what": boundary detector (hardest scientific value), candidate applications (honestly, mostly still arguments), route investment (stockpiling for the universal machine) — the special-purpose machine is the vanguard, not the throne.
Hook for the next stop: fifty chapters. The fifth batch wraps up with the traditional midterm review — spreading the algorithms, protocols, and lessons from five batches into a "capability map": a three-color map of what quantum machines can do, cannot do, and "don't know yet." 050: *Fifty Chapters Midterm Review: The Algorithm Capability Map*.
#QuantumComputing #FromCoinsToErrorCorrection #QuantumSampling #Jiuzhang