Transversal Gates & Eastin–Knill
No code has a transversal universal gate set.
Transversal gates are the gold standard of fault tolerance: no physical gate ever couples two qubits of the same block. If some code had a universal transversal gate set, fault-tolerant computing would be easy. Eastin and Knill proved in 2009 that no code does, with a one-page argument from Lie theory.
What you’ll learn
- Define transversal logical gates and list what standard codes offer.
- State and prove the Eastin–Knill theorem, pinpointing where error detection enters.
- Use the Clifford hierarchy and the Bravyi–König theorem to explain the limits of local topological codes.
- Compare the workarounds (magic states, code switching, gauge fixing, concatenation, approximate covariance) and how each escapes the theorem's hypotheses.
Transversal gates
Partition the physical system of a code block into subsystems (usually single qubits). A unitary is transversal if it factorizes as ; across several blocks, may act on the -th subsystem of each block. A transversal gate maps a single-subsystem error to a single-subsystem error, so it is automatically fault tolerant.
| Code | Transversal logical gates | Missing |
|---|---|---|
| Any CSS code | CNOT between blocks, Paulis | depends on the code |
| Steane , 2D color codes | the full Clifford group (, , CNOT) | |
| Reed–Muller , 3D color codes | , CNOT | |
| Surface code | CNOT; up to a rotation of the patch | , |
A continuous family of transversal gates would be ideal: rotations for all would give arbitrary logical rotations. The bit-flip code shows that this can happen, but only for a code that does not fully protect its qubit.
That continuum exists because the code cannot detect a single error: acts on the codespace as , not as a multiple of the identity. Eastin–Knill says this is the only way a continuum can arise.
The Eastin–Knill theorem
The transversal unitaries that preserve the code form a closed subgroup of the compact Lie group , hence a compact Lie group.
Restriction to the codespace is a continuous homomorphism: the logical action. We must show that its image is finite modulo phases.
The identity component is generated by one-parameter subgroups. Their generators lie in the Lie algebra of , which is , so is a sum of single-subsystem Hermitian terms .
Differentiating at gives . Here error detection enters: each acts on one subsystem, so .
Every element of acts on the code as a global phase: it is logically trivial.
A compact Lie group has finitely many connected components, so is finite, and the logical action modulo phases factors through it. Only finitely many logical gates arise. A finite group of unitaries on a space of dimension at least 2 is not dense in , so it is not universal.
Think first Does Eastin–Knill forbid a code from having a transversal non-Clifford gate such as ?
No. The Reed–Muller code has a transversal , and so do 3D color codes. The theorem only says the whole transversal group is finite, so it cannot be universal: the Reed–Muller code pays by lacking a transversal .
Topological codes and the Clifford hierarchy
Transversality is one kind of locality. Bravyi and König asked what constant-depth local circuits, which like transversal gates spread errors only a bounded distance, can do on topological codes. Recall the Clifford hierarchy: is the Pauli group and consists of unitaries that conjugate Paulis into ; is the Clifford group and .
For (surface and 2D color codes) this means at most Clifford gates: is out of reach without extra resources. In , the 3D color code's transversal saturates the bound. Pastawski and Yoshida (2015) extended such results to subsystem codes and related them to the code's distance and locality.
What does the Bravyi–König theorem imply for the 2D surface code?
- It has no fault-tolerant logical gates at all
- Its gate is transversal but its gate is not
- Constant-depth local circuits implement at most Clifford logical gates, so needs another mechanism such as magic states
- For large enough , constant-depth circuits become universal
Show the answer
C. Constant-depth local circuits implement at most Clifford logical gates, so needs another mechanism such as magic states
puts every constant-depth local logical gate in , the Clifford group. The surface code gets its gates from magic-state injection plus distillation or cultivation.
Working around Eastin–Knill
Every practical fault-tolerant scheme evades the theorem by dropping one of its hypotheses: somewhere, a gate is not a transversal unitary on a single fixed code.
| Workaround | Idea | Hypothesis it drops |
|---|---|---|
| Magic states (Knill, 2004; Bravyi & Kitaev, 2005) | Teleport in from distilled resource states | Not a unitary: uses ancillas, measurement and feed-forward |
| Code switching (Paetznick & Reichardt, 2013; Anderson, Duclos-Cianci & Poulin, 2014) | Move between the Steane code (transversal ) and the Reed–Muller code (transversal ) | No single code: the switch is a fault-tolerant, non-transversal procedure |
| Gauge fixing (Bombín, 2015) | Subsystem codes (gauge color codes) whose gauge choice changes which gates are transversal | The stabilizer group changes during the computation |
| Concatenated codes (Jochym-O'Connor & Laflamme, 2014) | Inner and outer codes with complementary transversal gates | Gates are transversal at one level, not on the physical qubits |
| Approximate codes | Codes covariant under a continuous group that correct errors only approximately | Exact error detection is replaced by approximate correction |
Key takeaways
- Transversal gates never spread errors within a block, but every code that detects single-subsystem errors has only a finite group of transversal logical gates (Eastin–Knill).
- Proof: generators of transversal, code-preserving unitaries are sums of single-subsystem terms; error detection makes them act as scalars on the code, so only the finitely many components of a compact Lie group survive.
- Bravyi–König: constant-depth local circuits on -dimensional topological stabilizer codes give only gates, so 2D codes need magic states (or similar) for .
- Workarounds each drop a hypothesis: magic states (measurement), code switching and gauge fixing (changing codes), concatenation (not physically transversal), approximate codes (error at least of order ).
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Which hypothesis must the code satisfy for Eastin–Knill to apply?
- It is a stabilizer code
- It detects arbitrary errors on any single subsystem
- It has distance at least 3
- It is geometrically local in 2D
Show the answer
B. It detects arbitrary errors on any single subsystem
Only single-subsystem error detection, , is needed. The theorem covers all codes, stabilizer or not, of distance at least 2.
In the proof, what does error detection guarantee about a generator of transversal, code-preserving unitaries?
- That
- That commutes with every Pauli operator
- That is a stabilizer
- That acts on the codespace as a multiple of the identity, so is logically a global phase
Show the answer
D. That acts on the codespace as a multiple of the identity, so is logically a global phase
. The whole identity component therefore acts trivially on the code, leaving only the finitely many components of a compact group.
How does code switching between the Steane and Reed–Muller codes evade Eastin–Knill?
- The switching step is not a transversal unitary on a single code; each code alone has a finite, non-universal transversal set
- One of the two codes fails to detect single-qubit errors
- It uses only Clifford gates
- It violates Eastin–Knill, which is why nobody uses it
Show the answer
A. The switching step is not a transversal unitary on a single code; each code alone has a finite, non-universal transversal set
The Steane code supplies transversal Cliffords and the Reed–Muller code a transversal . Neither set is universal, but together they are, and the conversion between the codes is a fault-tolerant procedure that is not transversal.
Which statement is consistent with Eastin–Knill?
- No code has a transversal gate
- The Steane code has a transversal gate
- The code has a transversal gate but no transversal
- Some codes that detect all single-qubit errors have a continuous family of transversal logical rotations
Show the answer
C. The code has a transversal gate but no transversal
Eastin–Knill forbids a universal (or continuous) transversal set, not individual non-Clifford gates. The Reed–Muller code trades for .
Further reading
- B. Eastin & E. Knill, "Restrictions on transversal encoded quantum gate sets", Phys. Rev. Lett. 102, 110502 (2009).
- B. Zeng, A. Cross & I. L. Chuang, "Transversality versus universality for additive quantum codes", IEEE Trans. Inf. Theory 57 (2011).
- S. Bravyi & R. König, "Classification of topologically protected gates for local stabilizer codes", Phys. Rev. Lett. 110, 170503 (2013).
- A. Paetznick & B. W. Reichardt, "Universal fault-tolerant quantum computation with only transversal gates and error correction", Phys. Rev. Lett. 111, 090505 (2013).
- P. Faist, S. Nezami, V. V. Albert, G. Salton, F. Pastawski, P. Hayden & J. Preskill, "Continuous symmetries and approximate quantum error correction", Phys. Rev. X 10, 041018 (2020).