The Eastin-Knill Theorem
No quantum code can implement a universal gate set transversally, forcing every fault-tolerant scheme to use a non-transversal technique for at least one gate.
Statement
The Eastin-Knill theorem, proved in 2009, says that for any quantum error-correcting code that detects at least one error, the set of gates implementable transversally forms a finite group. Since a universal gate set must be infinite (dense in the group of unitaries), no code can be both error-correcting and transversally universal. There is always at least one gate that resists transversal implementation.
Why the set is finite
The argument shows that transversal logical gates form a discrete, and hence finite, subgroup of the logical unitary group. Intuitively, transversal gates cannot generate continuous rotations of arbitrary small angle on the logical qubit, because any continuous family would let error information leak locally, contradicting the code's ability to keep logical information nonlocal. A finite group cannot approximate every unitary, so universality is impossible transversally.
- Transversal gates on any nontrivial code form a finite group.
- A finite group cannot be a universal (dense) gate set.
- Therefore some universal gate must use a non-transversal method.
- The obstruction is fundamental, not a limitation of specific codes.
Consequences and workarounds
This theorem is why fault-tolerant quantum computing is not simply a matter of stacking transversal gates. Every architecture needs a way to enact the missing gate, usually the non-Clifford T gate. The dominant solution is magic state distillation, which prepares a resource state fault-tolerantly and teleports the gate. Alternatives include code switching, where one moves between two codes each transversal for a different part of the gate set, gauge fixing in subsystem codes, and pieceable fault tolerance.
Eastin-Knill sharpens the picture of fault tolerance: transversality handles most gates for free, but a genuinely different and typically more expensive mechanism is always required to complete a universal set. That gap is a major driver of the overhead in real machines.