Fault tolerance: threshold theorem, magic state distillation, lattice surgery
Error correction is not enough on its own. The circuits that measure syndromes are made of the same faulty gates as everything else, and a gate applied to a code block could spread one error into several. Fault tolerance is the discipline of computing on encoded data so that errors never cascade. Its crowning result, proved independently by several groups in 1996–97, says that if every component fails less often than some threshold, arbitrarily long quantum computations are possible with only polylogarithmic overhead. The heart of the proof is one inequality.
On the plate: error rates through levels of encoding.
The threshold theorem by concatenation
Encode each qubit in a distance-3 code, and build every gadget so that one fault anywhere causes at most one error per block. Then a logical failure needs at least two faults, out of some number of fault locations: with . Now encode each physical qubit of that code again, and again. After levels,
Below threshold the error falls doubly exponentially in the number of levels, while the size grows only exponentially: polylogarithmic overhead. Set 10^-3.0 and 100. Dorit Aharonov and Michael Ben-Or; Emanuel Knill, Raymond Laflamme and Wojciech Zurek; and Alexei Kitaev proved versions in 1996–97. Topological codes such as the surface code reach the same conclusion without concatenation, with thresholds near 1%. Established
Magic states
By Eastin–Knill (Chapter 138), the surface code’s easy gates are Clifford gates, which a classical computer can simulate (Chapter 108). Universality needs a T gate, applied by consuming a magic state through a short teleportation circuit. Magic states prepared directly are noisy. Sergey Bravyi and Kitaev showed in 2005 how to distil them: 15 noisy copies go in, and the 15-qubit Reed–Muller code’s checks reject bad batches, so one cleaner copy comes out with error . Input error -3.0 (log₁₀). Two rounds take 10⁻³ to below 10⁻²⁰. Distillation factories once dominated every resource estimate. In 2024 Craig Gidney, Noah Shutty and Cody Jones proposed magic-state cultivation: grow a magic state inside a small code, checking it repeatedly, reaching about 2 × 10⁻⁹ error at 10⁻³ physical noise for roughly the cost of a CNOT. It has been benchmarked in simulation for state preparation; its place in full computations is still being worked out. Established for distillation; Debated for cultivation’s full role.
Lattice surgery
Surface-code patches cannot easily apply a transversal CNOT to each other on a flat chip. Dominic Horsman, Austin Fowler, Simon Devitt and Rodney Van Meter introduced lattice surgery in 2012: measure joint operators such as by temporarily merging two patches along a boundary for rounds, then splitting them. A CNOT becomes a sequence of joint measurements plus a classical correction. Daniel Litinski’s 2019 “A Game of Surface Codes” turned layout into a board game of tiles and time steps, and showed that a whole algorithm can be compiled into Pauli-product measurements and magic-state consumption. Watch the plate merge and split two patches. Established
What you now have
Fault-tolerant gadgets, the threshold theorem by concatenation and its doubly exponential suppression, magic states and 15-to-1 distillation, cultivation, and lattice surgery.
· · ·
Three questions to carry with you.
And one to work out. One round of 15-to-1 distillation with input error : output = ?
Sources: D. Aharonov and M. Ben-Or, Proc. 29th ACM STOC, 176 (1997). E. Knill, R. Laflamme and W. H. Zurek, Science 279, 342 (1998). A. Yu. Kitaev, Russ. Math. Surv. 52, 1191 (1997). S. Bravyi and A. Kitaev, Phys. Rev. A 71, 022316 (2005). C. Horsman, A. G. Fowler, S. Devitt and R. Van Meter, New J. Phys. 14, 123011 (2012). D. Litinski, Quantum 3, 128 (2019). C. Gidney, N. Shutty and C. Jones, arXiv:2409.17595 (2024). Checked by code: 35 × 10⁻⁹ = 3.5 × 10⁻⁸.