threshold theorem

In plain terms

Every physical component fails sometimes, and a long computation uses a great many of them, so the obvious worry about quantum computing is that errors accumulate faster than any code can remove them. Error correction on its own doesn't settle the worry, because the correction circuits are built from the same faulty components.

The threshold theorem settles it. Encode the computation in a code, then encode the encoded computation in the same code again, and repeat. Each level of encoding turns the error rate into roughly the square of itself times a constant that counts the ways a level can fail. If the starting rate is below the point where that map starts shrinking, which is the threshold, then repeated encoding drives the failure probability down doubly exponentially in the number of levels, so a handful of levels buys an enormous improvement.

What you pay is size. Each level multiplies the number of physical qubits and operations by a constant factor, and the number of levels you need grows only like the logarithm of the logarithm of the target accuracy, so the total overhead grows like a power of the logarithm of the circuit size. Polynomial slowdown is the standard currency of computer science, and a power of a logarithm is far cheaper than that, which is why the theorem is read as the statement that fault-tolerant quantum computing is possible in principle.

In CSD

The corpus proves the threshold statement at two levels of detail. At code capacity, where errors strike the qubits and the recovery is ideal, the Steane code's failure probability is at most twenty-one times the square of the physical rate, and concatenating gives the iterated bound with its doubly exponential decay below one twenty-first. At circuit level the counting is over a whole circuit of gadgets rather than one block: a union bound over the gadgets, then the concatenation recursion, and the result is that for any circuit size and any target accuracy there's a level at which the probability that anything anywhere fails falls below the target.

The overhead statement is proved in the same place, in the form the practical claim needs. The number of levels needed grows like the logarithm of the logarithm of the accuracy, so the size blow-up is bounded by a power of a logarithm of the circuit size. The honest boundary is that the gadgets are treated as ideal operations followed by faults, with the fault-tolerant syndrome-extraction circuit and the extended rectangle analysis kept as open rows, so what's proved is the counting half of fault tolerance rather than the circuit design half.

Mathematically

circuitMeasure is the product measure over the fault patterns of a circuit of N gadgets at concatenation level k, with circuitBad the event that some gadget fails. circuitMeasure_circuitBad_le is the union bound over gadgets composed with the code-capacity recursion of CodeCapacityThreshold.lean, whose concatenated bound is (c p)^(2^k) / c with c = 21 for the Steane code. exists_level_circuitMeasure_lt then gives, for c p < 1 and any target eps, a level k with circuitMeasure (circuitBad) < eps, through exists_level_mul_lt and the doubly exponential decay of (c p)^(2^k).

The overhead half is exists_level_two_pow_le and exists_level_overhead_le, stated with Real.logb and rpow: the required level is of order log log (1/eps), so 2^k, the size factor per encoded operation, is bounded by a power of log (N / eps). The Steane instance is steane_circuit_threshold, which feeds the code's 21 p^2 code-capacity bound into the generic statement.

The name

The threshold theorem was proved independently in 1996 and 1997 by Peter Shor, by Dorit Aharonov and Michael Ben-Or, by Emanuel Knill, Raymond Laflamme and Wojciech Zurek, and by Alexei Kitaev, and it changed the subject from a curiosity into an engineering programme. The numerical value of the threshold depends on the code, the noise model and the architecture, and modern estimates for surface codes sit near one error in a thousand operations.

Panos Aliferis, Daniel Gottesman and John Preskill later gave the extended rectangle analysis, which is the accounting scheme that makes the constant in the theorem trustworthy rather than merely finite.

Related entries

• concatenated codeConcatenation encodes a code inside itself, so each physical qubit of the outer block becomes a whole encoded block of its own, and the failure probability drops to roughly its own square at every level.
• Steane codeSeven qubits protect one, as the Steane code was the first to correct any single- qubit error by using the same classical Hamming code twice, once for bit flips and once for phase flips.
• transversal gateA transversal gate computes on encoded information by acting on each physical qubit separately, so a fault in one qubit stays in one qubit and the code keeps its protection while the computation runs.
• Knill-Laflamme conditionsQuantum error correction has an exact test, as a set of errors is correctable if and only if the code can't tell those errors apart, and that condition is a piece of algebra you can check before building any repair.
• magic-state distillationDistillation turns many noisy magic states into one clean one, by encoding them in a code whose checks reject the likely errors, and the error rate falls as the cube of itself at every round.