Peter Shor Saved Quantum Computing. Nobody Read the Fine Print.
The Longest Calculation: Quantum Computing, an Inside Story. Forthcoming Book. Episode VII
The last post ended with a cliffhanger. The physicists who showed how fast the environment destroys quantum information nearly killed the field. By 1995, serious people were concluding that large-scale quantum computing was impossible in principle. You cannot copy a qubit. You cannot inspect one without destroying it. And the environment corrupts them faster than any useful computation can run.
Peter Shor, the same mathematician whose factoring algorithm had made quantum computers worth building, published the rescue. He showed that you could spread the information in a single qubit across nine physical qubits in a way that made it recoverable even after some of them had been corrupted. You could measure auxiliary qubits to identify what went wrong without looking at the data itself. Andrew Steane in Oxford arrived at a similar scheme independently. Within a year, a field that had been declared dead had a theoretical toolkit for fighting the very problem that was supposed to kill it.
There was a catch. Error correction is itself a computation, performed by hardware that is itself noisy. The gates used to detect errors can introduce new errors. The measurements can be faulty. The corrections can be wrong. You are cleaning a window with a dirty cloth.
In November 1996, Dorit Aharonov and Michael Ben-Or at the Hebrew University of Jerusalem proved the theorem that answered this objection. The threshold theorem says: if the error rate per gate is below a certain constant, then arbitrarily long quantum computations can be performed with arbitrarily high reliability, at a cost that grows only modestly with the length of the computation. Below the threshold, correction outpaces corruption. The computation can, in principle, run forever.
The method is concatenation. Encode each logical qubit in several physical qubits. Use the encoded qubits to build better gates. Encode those gates in another layer of the same code. Each layer reduces the effective error rate, provided the physical rate stays below the threshold. Stack enough layers and the logical error rate drops as low as you need.
The price is qubits. Each layer multiplies the number of physical qubits required. For the early codes, at error rates near the threshold, the overhead was enormous: thousands of physical qubits for each logical qubit. Current estimates for the surface code, the most studied architecture, suggest that running Shor’s algorithm on a cryptographically relevant number would require millions of physical qubits. The best machines available today have a few thousand.
The theorem builders were careful about what their results implied. Preskill, in particular, was consistently honest about the gap between mathematical proof and physical reality. The theorems said: if the noise is below this level, fault tolerance works. The press releases said: fault tolerance works. The caveats were stripped away because caveats do not raise money.
The threshold theorem converted a question of principle into a question of degree. It moved quantum computing from "probably impossible" to "extremely hard." That single reclassification opened the funding gates. DARPA, the NSF, and eventually the intelligence agencies began writing checks. The first startups appeared. The word "scalable" entered the press releases, deriving its authority directly from a theorem that most of the people using the word had never read. Governments worldwide have since spent tens of billions of dollars on quantum computing. The fine print is still there, for anyone who cares to read it.
Update: The story of how the theorem's caveats stopped doing any work continues in Post 10