Achieving Universality with the Clifford Hierarchy

The trouble with universality and quantum error correction

It would be nice if we were certain that applying a finite sequence of gates could approximate any arbitrary quantum state — a property called universality [2]. However, Clifford gates such as the Hadamard $H$, Phase $S$, or CNOT gates and all Pauli gates \(\{X,Y,Z\}\) are not enough because they can only achieve \(90^{\circ}\) or \(180^{\circ}\) rotations on the Bloch sphere. That means, if you had a single qubit initially in the \(|0\rangle\) state, no matter the sequence of Clifford gates you apply, you can only ever reach 6 points on the Bloch sphere: the stabilizer states.

It turns out that all you need to achieve universal quantum computing are the Clifford gates and at least one non-Clifford gate [3]! In principle, you could select any non-Clifford gate, but a common gate set is (Clifford+T).

The T gate applies a \(45^{\circ}\) rotation about the $Z$ axis. On the surface, this doesn’t seem too special — but with the addition of a non-Clifford gate, the Solovay-Kitaev theorem guarantees that any state can be approximated by a finite sequence of gates. This gate sequence can be found via methods such as the Solovay-Kitaev algorithm [4] or gridsynth [5]. Putting all these pieces together, we can now obtain, say, a \(1^{\circ}\) rotation about the $Z$ axis to a \(10^{-2}\) error with a sequence of $T$, $H$, and $S$ gates.

For noisy intermediate-scale quantum (NISQ) computing, the story ends here. The problem arises when trying to achieve both universal and fault-tolerant quantum computing.

Realistic quantum hardware is noisy, and so quantum data must be protected with quantum error correction (QEC) codes to achieve fault-tolerance. Note that a fault-tolerant implementation of a quantum gate can be obtained for free if that gate can be implemented transversally, because transversal gates limit the propagation of errors. Many QEC codes such as the CSS, colour, surface, and qLDPC codes have transversal implementations of Clifford gates.

However, the Eastin-Knill theorem dictates that there can be no quantum error correction code that can implement both Clifford and non-Clifford gates transversally. Hence, the same QEC codes as above that implement Clifford gates fault-tolerantly cannot implement non-Clifford gates fault-tolerantly.

So, it appears that we are stuck: Either we perform fault-tolerant but non-universal quantum computing, or we perform universal but non-fault-tolerant quantum computing. Is there some way we can implement non-Clifford gates in these QEC codes fault-tolerantly and non-transversally?

If only there was some relationship between non-Clifford gates and Clifford gates that we can exploit…

Clifford and Pauli gate relations

The core idea of the Clifford hierarchy lurks beneath many of the concepts you may already know: relationships between different gates can be exploited to simplify computation. For example, Clifford-only quantum circuits are known to be efficiently simulatable classically, as proven by the Gottesman-Knill theorem.

Stabilizer tableau simulation is one such method. If $Z$ is a stabilizer corresponding to the state \(|0 \rangle\), then the application of a Clifford gate such as $H$ transforms the stabilizer to become \(HZH^{\dagger} = X\) corresponding to the new state \(H |0 \rangle = |+ \rangle\). For any Clifford gate, $C$, and for all Pauli gates \(P \in \{X,Y,Z\}\), observe that it is always true that the transformation \(CPC^{\dagger}\) yields a Pauli gate up to a global phase.

In other words, Clifford gates map Pauli gates to Pauli gates under conjugation. As my colleague wrote in this demo, one can exploit this fact to efficiently track how stabilizers evolve through a Clifford-only circuit. Pauli propagation exploits a similar idea to accelerate the classical calculation of circuits’ expectation values. Pauli frame tracking uses a similar idea to decouple the decoding step of quantum error correction from Clifford gate execution.

What do non-Clifford gates map Pauli gates to? Does that mapping help us simplify computation too?

The Clifford Hierarchy

It turns out that there is a structure connecting infinite classes of gates called the Clifford hierarchy [6]. Exploiting this hierarchy can help us implement any non-Clifford gate fault-tolerantly.

Achieving universal FTQC with the Clifford hierarchy

With the Clifford hierarchy, we can fault-tolerantly implement a \(\mathcal{C}_3\) gate with only \(\mathcal{C}_2\) gates via gate teleportation [6]. Gate teleportation builds on top of state teleportation à la Alice and Bob. Recalling that many QEC codes cannot implement a non-Clifford gate transversally, Alice cannot simply apply a transversal non-Clifford gate on her top qubit in Figure 1 without possibly introducing irrecoverable noise.

So, as shown in Figure 1, suppose we apply a gate \(U\in \mathcal{C}_3\) on Bob’s half of the Bell state pair on the bottom, and proceed with \(|\psi\rangle\) teleportation as usual. We won’t worry about how Bob can apply $U$ but Alice can’t just yet. Suffice to say, Bob has a magic state. 🪄

Upon measuring the top two qubits, like in standard state teleportation, a Pauli error $P$ occurs on the bottom qubit. There is an equal chance of \(P \in \{X,Y,Z,I\}\) occurring. For state teleportation, applying \(P^{\dagger}=P\) removes that error. However, the difference here with gate teleportation is that Bob applied $U$ already. So, after measurement, the bottom qubit becomes \(UP|\psi\rangle\). Applying \(P^{\dagger}\) does not remove the Pauli error.

To see how we can overcome this, let’s apply the identity \(I=U^{\dagger} U\) to obtain \(UP I |\psi\rangle = UPU^{\dagger}U|\psi\rangle = CU|\psi\rangle\). Observe that this method has reversed the order of the gates so that $C$ is now exposed while $U$ is applied to the state \(|\psi\rangle\) first. By the Clifford hierarchy, $C$ must be a Clifford gate. As discussed above, many QEC codes can implement Clifford gates fault-tolerantly. Thus, with the knowledge of $P$ from the Bell state measurement, \(C^{\dagger} = UPU^{\dagger} = C\) can be applied to produce \(U|\psi\rangle\), the desired non-Clifford gate. This procedure, known as magic state injection, generalises to the n-qubit case.

An example code for a $C_3$ teleportation circuit is given below:

import pennylane as qp
import numpy as np

dev = qp.device('default.qubit', wires=3)
initial_state = np.array([1, 1]) / np.sqrt(2) # arbitrary initial state

# Define your C_3 gate here.
# We chose a T gate. Feel free to change it.
def target_gate(wire):
    qp.T(wires=wire)

@qp.qnode(dev)
def universal_teleportation(state):
    qp.StatePrep(state, wires=0) # initialise the state

    # Prepare magic state using the bottom 2 qubits
    qp.H(1)
    qp.CNOT(wires=[1, 2])
    target_gate(2) # Apply the C_3 gate

    # Teleport
    qp.CNOT(wires=[0, 1])
    qp.H(0)

    # Measure
    m0 = qp.measure(0) # Z error
    m1 = qp.measure(1) # X error

    # We must handle U P U^dagger corrections
    def x_corr():
        qp.adjoint(target_gate)(2)
        qp.X(2)
        target_gate(2)

    def z_corr():
        qp.adjoint(target_gate)(2)
        qp.Z(2)
        target_gate(2)

    def xz_corr():
        qp.adjoint(target_gate)(2)
        qp.X(2)
        qp.Z(2)
        target_gate(2)

    # 3. Apply conditionally
    qp.cond(m1 & (m0 == 0), x_corr)() # If we measure |01>
    qp.cond(m0 & (m1 == 0), z_corr)() # If we measure |10>
    qp.cond(m0 & m1, xz_corr)() # If we measure  |11>

    return qp.density_matrix(wires=2)

Let’s now check the circuit gives the expected result, by computing the correct answer directly from the density matrix:

U_mat = qp.matrix(target_gate, wire_order=[0])(0)
initial_dm = np.outer(initial_state, np.conj(initial_state))
correct_answer = U_mat @ initial_dm @ np.conj(U_mat).T
print(correct_answer)

[[0.5       +0.j         0.35355339-0.35355339j]
 [0.35355339+0.35355339j 0.5       +0.j        ]]

Comparing this to our universal teleportation circuit, we can see that it matches:

result = universal_teleportation(initial_state)
print(result)
print(np.allclose(result, correct_answer))

[[0.5       +0.j         0.35355339-0.35355339j]
 [0.35355339+0.35355339j 0.5       +0.j        ]]
True

Observe that \((UPU^{\dagger})^{\dagger}\) in practice is implemented as simply the reverse of the conjugation.

The challenge of implementing the \(\mathcal{C}_3\) gate, $U$, fault-tolerantly has been shifted to fault-tolerantly preparing the magic state \((I \otimes U)(|00\rangle+|11\rangle)/\sqrt{2}\) offline. The key idea is: We can prepare numerous, potentially noisy, candidate magic states in advance, and only allow the sufficiently clean states to be consumed to enable teleportation. Although magic states are a broader idea, the term is often used to mean magic states for $T$ gates specifically. There are a few ways to prepare magic states fault-tolerantly such as magic state distillation. The remainder of the circuit consists of Clifford (\(\mathcal{C}_2\)) gates and Bell basis measurements, which have fault-tolerant implementations in common QEC codes. Therefore, we can fault-tolerantly implement both Clifford and non-Clifford gates despite the Eastin-Knill theorem!

What is more, this teleportation circuit provides a systematic method to teleport any \(\mathcal{C}_k\) gate, so long as you have access to \(\mathcal{C}_{k-1}\) gates. If \(\mathcal{C}_{k-1}\) gates are not fault-tolerantly implemented in your QEC code of choice, then you may use additional teleportation circuits that produce lower level gates until you reach the fault-tolerant gate set. Figure 2 below shows an example of nested teleportation circuits to implement a \(\mathcal{C}_4\) gate for a QEC code that transversally implements Clifford gates. The first Bell basis measurement applies \(C_4 \in \mathcal{C}_4\) with some Pauli error $P_4$. Conjugation implies we must apply \(C_3^{\dagger} = (C_4 P_4 C_4^{\dagger})^{\dagger} = C_3 \in\mathcal{C}_3\) correction gate. For a QEC code that does not implement this type of gate transversally, we use another teleportation circuit. That teleportation circuit induces a Pauli error $P_3$ that must be corrected in the manner described above. It can be confirmed through computation that the final result is \(C_4 |\psi\rangle\).

An example code that implements this doubly-nested $C_4$ teleportation circuit is below:

import pennylane as qp
import jax.numpy as jnp
from catalyst import qjit

dev = qp.device('lightning.qubit', wires=5)

def conjugate(gate_fn, pauli_fn):
    # Applies U  P  U^dagger
    def conjugated_gate(wire):
        qp.adjoint(gate_fn)(wire)
        pauli_fn(wire)
        gate_fn(wire)
    return conjugated_gate

# Helper redefinitions
def pauli_x(wire): qp.X(wire)
def pauli_z(wire): qp.Z(wire)
def pauli_xz(wire):
    qp.X(wire)
    qp.Z(wire)

# Define the C_4 gate. We chose sqrt(T) here.
# Feel free to change it
def l4_gate(wire):
    qp.PhaseShift(jnp.pi / 8, wires=wire)

# Automatically generate C_3 corrections (C_4 P_4 C_4^\dagger)
l3_x_corr = conjugate(l4_gate, pauli_x)

# Automatically generate C_2 corrections for the nested C_3 (C_3 P_3 C_3^\dagger)
l2_z_corr = conjugate(l3_x_corr, pauli_z)
l2_x_corr = conjugate(l3_x_corr, pauli_x)
l2_xz_corr = conjugate(l3_x_corr, pauli_xz)

# Nested teleportation
@qjit
@qp.qnode(dev)
def c4_teleportation(state):
    qp.StatePrep(state, wires=0)

    # C_4 Teleportation
    qp.Hadamard(1)
    qp.CNOT(wires=[1, 2])
    l4_gate(2)

    qp.CNOT(wires=[0, 1])
    qp.Hadamard(0)

    m0 = qp.measure(0)
    m1 = qp.measure(1)

    # 2. Nested C_3 Teleportation
    def apply_nested_l3_correction():
        qp.Hadamard(3)
        qp.CNOT(wires=[3, 4])

        # Apply C_3 = C_4 P_4 C_4^\dagger
        l3_x_corr(4)

        qp.CNOT(wires=[2, 3])
        qp.Hadamard(2)

        n0 = qp.measure(2)
        n1 = qp.measure(3)

        # Apply C_2 = C_3 P_3 C_3^\dagger
        def apply_z(): l2_z_corr(4)
        def apply_x(): l2_x_corr(4)
        def apply_xz(): l2_xz_corr(4)

        qp.cond(n0 & (n1 == 0), apply_z)()
        qp.cond(n1 & (n0 == 0), apply_x)()
        qp.cond(n0 & n1, apply_xz)()

        qp.cond(m0 == 1, pauli_z)(4)

    def skip_nested_l3_correction():
        qp.cond(m0 == 1, pauli_z)(2)
        qp.SWAP(wires=[2, 4])

    # 3. Branching Execution
    qp.cond(m1 == 1, apply_nested_l3_correction, skip_nested_l3_correction)()

    return qp.state()

What is the expected correct density matrix?

initial_state = jnp.array([1, 1]) / jnp.sqrt(2) # arbitrary initial state
correct_state = qp.matrix(l4_gate, wire_order=[0])(0) @ jnp.expand_dims(initial_state, axis=1)
correct_density_matrix = jnp.outer(correct_state , jnp.conj(correct_state))
print(jnp.round(correct_density_matrix , 3))

[[0.5  +0.j    0.462-0.191j]
 [0.462+0.191j 0.5  -0.j   ]]

Let us see if the circuit produces the same density matrix. Indeed, we can see that the results match.

output_state = qp.math.reduce_statevector(c4_teleportation(initial_state), indices=[4])
print(jnp.round(output_state , 3))
print(np.allclose(output_state, correct_density_matrix))

[[0.5  +0.j    0.462-0.191j]
 [0.462+0.191j 0.5  +0.j   ]]
True

Most generally, this teleportation circuit can be applied indefinitely to apply arbitrarily high level gates using the same idea outlined in Figure 2. Figure 3 below illustrates this idea artistically. It’s turtles all the way down!

Teleportation is more efficient with semi-Clifford gates

While the universal teleportation circuit above can implement any non-Clifford gate in the Clifford hierarchy fault-tolerantly, it still isn’t clear why the $T$ gate is commonly used to enable universality. To see that, let’s be greedy: How can we teleport gates more efficiently?

If a gate is semi-Clifford i.e., it can be written as $U = G_b V G_a$, where $V$ is a diagonal matrix in \(\mathcal{C}_k\) and $G_a$ and $G_b$ are each Clifford gates, then the resource cost of gate teleportation can be halved [7]. All one- and two-qubit gates in \(\mathcal{C}_k\) are semi-Clifford, as are three-qubit gates in \(\mathcal{C}_3\) [8]. Importantly, the $T$ gate is diagonal, which is a subset of semi-Clifford gates with $G_b = G_a = I$.

To explain why semi-Clifford gates can be teleported more efficiently, we firstly depict these more efficient ‘one-bit’ teleportation circuits. There are two such flavours: $Z$-teleportation and $X$-teleportation, named after the classically controlled correction these circuits apply. Figure 4a depicts the general one-bit $Z$-teleportation circuit for $U$, Figure 4b depicts the general one-bit $X$-teleportation circuit for $U$, and Figure 4c depicts the one-bit teleportation circuit for the $T$ gate. The section within the dashed box is a magic state.

Here, conjugating the $U$ gate across the \(D \in \{Z,X\}\) Pauli error creates the term \(UDU^{\dagger}\), which must be Clifford if $U$ is in \(\mathcal{C}_3\) and $D$ is Pauli as per the Clifford hierarchy. Semi-Clifford-ness allows us to move the $U$ gate to before the CNOT gate. Just as before, the part of the circuit up to the $U$ gate is called a magic state, which can be prepared in advance. Therefore, if the magic state is available, then a semi-Clifford gate such as the $T$ gate can be implemented fault-tolerantly.

The one-bit teleportation protocol halves the number of ancilla qubits, measurements, and gates compared to the general two-bit teleportation protocol above. Note that the diagonal $V$ in $U = G_b V G_a$ need not commute with the CNOT gates because you are always free to select $X$-teleportation. All diagonal gates commute with the control part of a CNOT gate. For this reason, this circuit can implement a controlled-Hadamard gate, which does not commute with CNOT [7].

Recursive application of this one-bit teleportation circuit leads to the implementation of semi-Clifford \(\mathcal{C}_k\) gates. Figure 5 illustrates an example of X-teleportation of a semi-Clifford \(C_4\in\mathcal{C}_4\) gate assuming that only \(\mathcal{C}_2\) gates are implemented transversally. This means we must use two teleportation circuits in total.

Now, we have an efficient method to teleport certain non-Clifford gates!

So, what’s so special about the T gate?

Adding any non-Clifford gate to a set of Clifford gates provides universality. The $T$ gate often appears as the non-Clifford gate of choice, but it’s just a \(45^{\circ}\) rotation about the $Z$ axis. What’s so special about the $T$ gate? Why not a gate that implements a \(1^{\circ}\) rotation? Or why not a Toffoli or a controlled-phase gate?

Gates above \(\mathcal{C}_3\) in the Clifford hierarchy are eliminated because they require more resources to implement because of the need for nested teleportation circuits, as shown in the above figures.

Within \(\mathcal{C}_3\), we should restrict ourselves to semi-Clifford gates to let us use the more efficient teleportation circuits. That means we should only consider one-, two-, or three-qubit gates [8], such as the $T$ gate, controlled-phase gate, controlled-Hadamard gate, and Toffoli gate. The gate that requires the fewest resources overall is the $T$ gate because it is a single-qubit diagonal gate (i.e., $G_a=G_b=I$). With these arguments, it is clear why the $T$ is often the non-Clifford gate of choice.

One can inject a $T$ gate via the circuit presented in Figure 4c, or using the circuit below. Additional explanation of the circuit below can be found in this magic states glossary entry.

Conclusion

We have seen how the Clifford hierarchy enables universal and fault-tolerant quantum computing by mapping higher level gates down to lower level gates. The same hierarchy also ranks gates by the number of resources needed to implement them fault-tolerantly, thus how ‘quantum’ they are and how gates can be considered as magic fuel for fault-tolerance.

Although the Clifford hierarchy was first proposed in the context of universality [6], its ideas lurk underneath other topics. For example, Pauli frame tracking conjugates Clifford gates to avoid having to physically execute correction Pauli gates [10].

Not only $T$ gates can be implemented fault-tolerantly; the Clifford hierarchy shows how an enormous class of gates can be implemented fault-tolerantly. For example, the diagonal $C-U$ gates that perform period finding for Shor’s algorithm , the quantum Fourier transform, and in quantum phase estimation (QPE) can be implemented fault-tolerantly using the teleportation circuits shown in the above sections.

References