Midway Review at 50 Posts: The Algorithm Capability Map
> Navigation note: Ideally you've read the previous 49 posts — this one is their group photo. > Next episode preview: 051, "Where Errors Come From: T1, T2, and Lifetime Tables" (opening of Batch Six).
The old cartographers' rule: draw solid lines around surveyed territory, mark impassable regions in red, and leave blank the unexplored seas with a note reading "here be dragons."
The column has reached exactly fifty posts — the halfway point. Following the cartographers' rule, this review lays out everything accumulated across the first five batches into a three-color capability map: the Green Zone (within quantum machines' reach, backed by theorems or demonstrations), the Red Zone (out of reach, also backed by theorems), and the White Zone (still unknown — here be dragons). The point of the review is not nostalgia: every step of the second half will be placed on this map.
Green Zone: The Real Territory of Quantum Machines
① Breaking one class of cryptography (Shor, posts 037–039). Factoring and discrete logarithms — the two foundations of public-key cryptography — have been mathematically dismantled. The engineering requires a fault-tolerant machine (millions of physical qubits), but the theorem is in hand; only engineering remains.
② Square-root speedup for unstructured search (Grover, posts 033/034). A thousand drawers in the time of a million; √N has been proven a physical limit — a rare patch of the Green Zone where even the ceiling has been measured.
③ Playing quantum systems (posts 042/043). Chemical ground states, material properties — quantum simulation ranks first among the reasons quantum machines exist: classical ledgers explode exponentially, quantum ledgers live there natively. Flagship targets (nitrogenase, superconductors) wait for error correction; toy demos are already running.
④ Sampling advantage (special-purpose machines, post 049). Machines like "Jiuzhang" and "Zuchongzhi" turned "quantum beats classical on certain tasks" from conjecture into repeatable, testable physical evidence — the tug-of-war continues, but the boundary has been crossed.
⑤ True randomness (post 029) and quantum communication (posts 025/026, 063 previewed). QRNG chips are already in phones; key distribution's "eavesdropping always leaves a trace" is commercially deployed — the two patches of the Green Zone closest to ordinary people.
⑥ Reading global properties of black boxes (posts 031/032/035). The Deutsch–Jozsa, Bernstein–Vazirani, and Simon family: reading a property in one query, one query for n, exponential period-finding — small but razor-sharp "mathematical scalpels."
Red Zone: Surveyed and Impassable
① The dead end of unstructured brute force (post 034). For NP-hard problems, quantum offers only a despairing square root — 2^1000 becomes 2^500, despair in a different pose. "Quantum as universal accelerator" is the Red Zone's first boundary marker.
② Copying unknown states (post 028). Sealed by a five-step proof by contradiction; the security of quantum money and cryptography rests entirely on this marker.
③ Faster-than-light signaling (posts 003/027). Bell's lawsuit was won, the no-communication theorem still holds — correlations act at a distance, information does not.
④ Reading the full picture of a quantum state (posts 016/046). One measurement collapses it; "solving the equation" is not the same as "seeing the answer" — sampling-and-estimation is the only form of quantum delivery.
⑤ Shallow circuits beating machine learning (post 048). The cheap-substitute crisis: QML whose encoding never enters exponential Hilbert space admits classical simulation of the same order — the newest boundary marker in already-falsified territory.
White Zone: Here Be Dragons
① The quantum status of NP-complete problems. The true relationship between BQP and NP (seeded twice, posts 040/046) — one of complexity theory's deepest open questions.
② Hidden subgroups in general groups. The QFT has no efficient circuit on graph-symmetry groups (post 040) — graph isomorphism and similar problems are stuck here.
③ Whether qRAM will ever be practical (posts 046/047). The data-loading crane, deciding whether an entire class of exponential speedups ever cashes out.
④ The engineering limits of error correction. When can the bill of millions of physical qubits supporting thousands of logical qubits be paid (posts 038/039) — the entire plot of Batches Six through Eight.
⑤ The real boundary of quantum machine learning. How far the "quantum data + quantum machine" front line can advance (post 048).
Five Ballast Lessons
Five sentences kept surfacing across fifty posts:
1. Interference is the only source of computational power (posts 004/013/016) — not superposition, not parallelism; it is "making the wrong answers cancel and the right answers reinforce." 2. Measurement is the toll (posts 016/002) — reading means collapse; sampling-and-estimation is the only form of quantum delivery. 3. Promises buy speedups (posts 034/040) — generality and brute-force speedup trade off; no algorithm is both universal and ferocious. 4. Account end to end (posts 046/048) — a fast kernel is not a usable system; loading and readout are two bridges you must cross. 5. Two calendars (post 039) — the theorem calendar of mathematics and the delivery calendar of engineering run on separate schedules; mixing them up leads to being fooled.
Taking the Analogy Apart
Where the three-color map borrows — and breaks:
- Disanalogy one: geographic borders stay put for millennia; capability boundaries drift with technology — the Green Zone expands (every step in error correction adds green), while "theorem-grade" markers in the Red Zone are stable and "evidence-grade" ones can shift.
- Disanalogy two: maps draw space; this map draws "task space" — the same task can change color with a different encoding or a different baseline (the substitutes and anti-substitutes of post 048). Colors carry dates; read the legend's year first.
Luggage to Take Home
1. The three-color map: green (code-breaking / √N search / quantum simulation / sampling advantage / true randomness / black-box properties), red (brute-force dead end / no-cloning / no FTL / no full state readout / shallow-circuit QML), white (NP status / general groups / qRAM / error-correction limits / QML boundaries). 2. Five ballast lessons: interference is the only power source, measurement is the toll, promises buy speedups, account end to end, two calendars — every post in the second half will use at least one. 3. How to read the halfway point: Batches One–Two gave intuition and tools, Batch Three gave craft, Batches Four–Five gave algorithms and the map — the second half (error correction, hardware, ecosystem, frontiers, practice) is entirely the process of turning this map green.
Batch Five closes here; the column is halfway done. The second half starts with the hardest piece: everything big in the Green Zone (Shor, chemistry, universal advantage) rests on the same prerequisite — error correction. And error correction begins with a question so plain it is almost brutal: where do errors come from, what do they look like, how fast do they kill? Post 051: "Where Errors Come From: T1, T2, and Lifetime Tables."
Tags: quantum-computing · from-coins-to-error-correction · capability-map · midway-review