Simple Algorithm
Quantum Computing · Rydberg State · 28 min

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 H=⨂j=1nHj\Hil=\bigotimes_{j=1}^n\Hil_j (usually single qubits). A unitary is transversal if it factorizes as U=⨂jUjU=\bigotimes_jU_j; across several blocks, UjU_j may act on the jj-th subsystem of each block. A transversal gate maps a single-subsystem error to a single-subsystem error, so it is automatically fault tolerant.

CodeTransversal logical gatesMissing
Any CSS codeCNOT between blocks, Paulisdepends on the code
Steane [[7,1,3]][[7,1,3]], 2D color codesthe full Clifford group (HH, SS, CNOT)TT
Reed–Muller [[15,1,3]][[15,1,3]], 3D color codesTT, CNOTHH
Surface codeCNOT; HH up to a rotation of the patchSS, TT

A continuous family of transversal gates would be ideal: rotations ⨂je−iθhj\bigotimes_je^{-i\theta h_j} for all θ\theta 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 ZZ error: Z1Z_1 acts on the codespace as Zˉ\bar Z, not as a multiple of the identity. Eastin–Knill says this is the only way a continuum can arise.

The Eastin–Knill theorem

DerivationProof
  1. G={U=⨂jUj : UPU†=P}\mathcal{G} = \Big\{U=\textstyle\bigotimes_j U_j\ :\ UPU^\dagger = P\Big\}

    The transversal unitaries that preserve the code form a closed subgroup of the compact Lie group ∏jU(Hj)\prod_jU(\Hil_j), hence a compact Lie group.

  2. ρ: G→U(C),ρ(U)=U∣C\rho:\ \mathcal{G}\to U(\mathcal{C}),\qquad \rho(U)=U\big|_{\mathcal{C}}

    Restriction to the codespace is a continuous homomorphism: the logical action. We must show that its image is finite modulo phases.

  3. U(t)=e−itK∈G0,K=∑jhjU(t)=e^{-itK}\in\mathcal{G}_0,\qquad K=\sum_j h_j

    The identity component G0\mathcal{G}_0 is generated by one-parameter subgroups. Their generators lie in the Lie algebra of ∏jU(Hj)\prod_jU(\Hil_j), which is ⨁ju(Hj)\bigoplus_j\mathfrak{u}(\Hil_j), so KK is a sum of single-subsystem Hermitian terms hjh_j.

  4. [K,P]=0 ⟹ K∣C=PKP=∑jPhjP=(∑jc(hj))P[K,P]=0\ \Longrightarrow\ K\big|_{\mathcal{C}} = PKP = \sum_j Ph_jP = \Big(\sum_j c(h_j)\Big)P

    Differentiating U(t)PU(t)†=PU(t)PU(t)^\dagger=P at t=0t=0 gives [K,P]=0[K,P]=0. Here error detection enters: each hjh_j acts on one subsystem, so PhjP=c(hj)PPh_jP=c(h_j)P.

  5. ρ(e−itK)=e−it∑jc(hj) IC\rho\big(e^{-itK}\big) = e^{-it\sum_j c(h_j)}\,\id_{\mathcal{C}}

    Every element of G0\mathcal{G}_0 acts on the code as a global phase: it is logically trivial.

  6. A compact Lie group has finitely many connected components, so G/G0\mathcal{G}/\mathcal{G}_0 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 SU(dim⁡C)SU(\dim\mathcal{C}), so it is not universal. □\square

Think first Does Eastin–Knill forbid a code from having a transversal non-Clifford gate such as TT?

No. The [[15,1,3]][[15,1,3]] Reed–Muller code has a transversal TT, 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 HH.

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: C(1)\mathcal{C}^{(1)} is the Pauli group and C(k+1)\mathcal{C}^{(k+1)} consists of unitaries that conjugate Paulis into C(k)\mathcal{C}^{(k)}; C(2)\mathcal{C}^{(2)} is the Clifford group and T∈C(3)T\in\mathcal{C}^{(3)}.

For D=2D=2 (surface and 2D color codes) this means at most Clifford gates: T∈C(3)T\in\mathcal{C}^{(3)} is out of reach without extra resources. In D=3D=3, the 3D color code's transversal TT saturates the bound. Pastawski and Yoshida (2015) extended such results to subsystem codes and related them to the code's distance and locality.

Check your understanding

What does the Bravyi–König theorem imply for the 2D surface code?

  1. It has no fault-tolerant logical gates at all
  2. Its TT gate is transversal but its HH gate is not
  3. Constant-depth local circuits implement at most Clifford logical gates, so TT needs another mechanism such as magic states
  4. For large enough dd, constant-depth circuits become universal
Show the answer

C. Constant-depth local circuits implement at most Clifford logical gates, so TT needs another mechanism such as magic states

D=2D=2 puts every constant-depth local logical gate in C(2)\mathcal{C}^{(2)}, the Clifford group. The surface code gets its TT 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.

WorkaroundIdeaHypothesis it drops
Magic states (Knill, 2004; Bravyi & Kitaev, 2005)Teleport TT in from distilled resource statesNot a unitary: uses ancillas, measurement and feed-forward
Code switching (Paetznick & Reichardt, 2013; Anderson, Duclos-Cianci & Poulin, 2014)Move between the Steane code (transversal HH) and the Reed–Muller code (transversal TT)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 transversalThe stabilizer group changes during the computation
Concatenated codes (Jochym-O'Connor & Laflamme, 2014)Inner and outer codes with complementary transversal gatesGates are transversal at one level, not on the physical qubits
Approximate codesCodes covariant under a continuous group that correct errors only approximatelyExact error detection is replaced by approximate correction

Key takeaways

  • Transversal gates ⨂jUj\bigotimes_jU_j 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 DD-dimensional topological stabilizer codes give only C(D)\mathcal{C}^{(D)} gates, so 2D codes need magic states (or similar) for TT.
  • 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 1/n1/n).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Which hypothesis must the code satisfy for Eastin–Knill to apply?

  1. It is a stabilizer code
  2. It detects arbitrary errors on any single subsystem
  3. It has distance at least 3
  4. It is geometrically local in 2D
Show the answer

B. It detects arbitrary errors on any single subsystem

Only single-subsystem error detection, PEP=c(E)PPEP=c(E)P, is needed. The theorem covers all codes, stabilizer or not, of distance at least 2.

Question 2

In the proof, what does error detection guarantee about a generator K=∑jhjK=\sum_jh_j of transversal, code-preserving unitaries?

  1. That K=0K=0
  2. That KK commutes with every Pauli operator
  3. That KK is a stabilizer
  4. That KK acts on the codespace as a multiple of the identity, so e−itKe^{-itK} is logically a global phase
Show the answer

D. That KK acts on the codespace as a multiple of the identity, so e−itKe^{-itK} is logically a global phase

PKP=∑jPhjP=(∑jc(hj))PPKP=\sum_jPh_jP=\big(\sum_jc(h_j)\big)P. The whole identity component therefore acts trivially on the code, leaving only the finitely many components of a compact group.

Question 3

How does code switching between the Steane and Reed–Muller codes evade Eastin–Knill?

  1. The switching step is not a transversal unitary on a single code; each code alone has a finite, non-universal transversal set
  2. One of the two codes fails to detect single-qubit errors
  3. It uses only Clifford gates
  4. 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 TT. Neither set is universal, but together they are, and the conversion between the codes is a fault-tolerant procedure that is not transversal.

Question 4

Which statement is consistent with Eastin–Knill?

  1. No code has a transversal TT gate
  2. The Steane code has a transversal TT gate
  3. The [[15,1,3]][[15,1,3]] code has a transversal TT gate but no transversal HH
  4. Some codes that detect all single-qubit errors have a continuous family of transversal logical rotations
Show the answer

C. The [[15,1,3]][[15,1,3]] code has a transversal TT gate but no transversal HH

Eastin–Knill forbids a universal (or continuous) transversal set, not individual non-Clifford gates. The Reed–Muller code trades HH for TT.

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).