There are many ways to perform fault tolerant quantum gates: lattice surgery, state injection and gate teleportation, braiding, gauge fixing, code deformation… the list goes on. But, by a large margin, people’s favorite way to do a fault tolerant gate is transversally. A transversal logical gate G is performed by broadcasting the physical gate G over the physical qubits making up the logical qubit.

As you will hear stated in almost any talk about fault tolerant quantum gates, the Eastin-Knill theorem proves that no error correcting code has a universal set of transversal gates. We must perform some gates non-transversally. We can’t always get what we want.

…or can we?

A Code with Universal Transversal Gates

The 15 qubit quantum Reed-Muller code is a very famous quantum error correcting code. Its main claim to fame is that it’s the simplest code with a transversal T gate, making it the foundation of 15-to-1 T state distillation.

The quantum Reed-Muller code also has some other transversal gates. It has transversal Pauli gates and, because it’s a CSS code with a single logical qubit, has transversal X-basis measurement, Z-basis measurement, and Controlled-NOT.

Putting together an incomplete inventory, the quantum Reed-Muller code has the following transversal gates:

Transversal bit flip (X)
Transversal T (T)
Transversal X-basis measurement (MX)
Transversal Z-basis measurement (MZ)
Transversal Controlled-NOT (CX)

…and we’re done. The above gateset is universal. We’ve violated the claim that no error correcting code has a universal set of transversal gates.

You don’t believe me? It’s easy to prove. A much better known universal gateset is Clifford+T, which is generated by the gates H, S, CX, T, MZ. The quantum Reed-Muller code already has transversal CX, T, and MZ so all we need to show is that we can synthesize S and H from X,T,MX,MZ,CX.

Getting S is trivial, because $S = T^2$. It’s almost not even worth mentioning:

Getting H is a bit trickier. It’s easiest to understand the decomposition if we first get SQRT_X. We can perform SQRT_X by using MX and S to prepare an $|i\rangle$ state and then consuming that state in a gate teleportation:

You can verify this identity using Stim:

import stim
assert stim.Circuit("""
    MX 1
    X 0
    S 1
    CX 1 0
    MX 1
    
    # Pauli feedback.
    CX rec[-2] 0
    CX rec[-1] 0
""").has_all_flows(stim.gate_data("SQRT_X").flows)

Once you have S and SQRT_X it’s easy to get H because $H = S \cdot \sqrt{X} \cdot S$:

You can also verify this identity using Stim:

import stim
assert stim.Circuit("""
    S 0
    MX 1
    X 0
    S 1
    CX 1 0
    MX 1
    CX rec[-2] 0
    CX rec[-1] 0
    S 0
""").has_all_flows(stim.gate_data("H").flows)

QED. The quantum Reed-Muller code can implement Clifford+T transversally, therefore the quantum Reed-Muller code has a universal transversal gate set, therefore everything is amazing.

…or is it?

The Catch

If you actually attempt to perform logical computations using these transversal gates, you will find that there is a problem. In the H decomposition, there is an MX immediately followed by a T (inside of an S). But the T is only safe to do if you’re in the code state, and the MX gate destroys the Z basis stabilizers of the code. Therefore, although both gates are individually transversal, the combination of the two is not. They need to be separated by multiple rounds of stabilizer measurements, to restore the lost stabilizers.

I would argue this is a knockdown argument that we should not consider the MX gate to be truly transversal. Transversal gates are supposed to preserve the code state, and MX does not. It is at best conditionally transversal; it can be done transversally if certain conditions are met (e.g. no other gates nearby).

As for the Eastin-Knill theorem, it’s actually fine (happy April Fools!). What the theorem states (according to Wikipedia) is “No quantum error correcting code can have a continuous symmetry which acts transversely on physical qubits”. This is crucially different from what people usually say the theorem states (that no universal transversal gate set exists). In particular, gate decompositions that involve dissipative gates and ancilla qubits can be universal without being continuous symmetries. The SQRT_X decomposition shown above is a good example.

So, in the end, we’re back where we started. We can declare that MX isn’t transversal, preserving the claim that no universal transversal gate set exists. Or we can say MX is transversal, and lose the notion that transversal gates are beautifully simple. Either way, we can’t always get what we want. Damn.

On Eastin-Knill Being Wrong

A Code with Universal Transversal Gates

The Catch