Controlling error propagation

Fault-tolerant quantum computation is akin to a race between errors and error correction. If the number of errors is small enough, error correction will successfully correct them; but if there are too many errors, error correction will fail.

For this reason, sufficient care must be given to the way quantum computations are performed in fault-tolerant implementations of circuits, to control error propagation. That is, an error on one qubit can potentially be propagated to multiple qubits through the action of gates in a quantum circuit, which can cause the number of errors to increase dramatically. This is a paramount concern, for if we don't manage to control error propagation, our error-correction efforts will quickly be overwhelmed by errors. If, on the other hand, we're able to keep the propagation of errors under control, then error correction stands a fighting chance of keeping up, allowing errors to be corrected at a high enough rate to allow the quantum computation to function as intended.

The starting point for a technical discussion of this issue is the recognition that two-qubit gates (or multiple-qubit gates more generally) can propagate errors, even when they function perfectly. For instance, consider a controlled-NOT gate, and suppose that an $X$ error occurs on the control qubit just prior to the controlled-NOT gate being performed. As we already observed in the "Correcting quantum errors" lesson, this is equivalent to an $X$ error occurring on both qubits after the controlled-NOT is performed. And the situation is similar for a $Z$ error acting on the target rather than the control prior to the controlled-NOT gate being performed.

This is a propagation of errors, because the unfortunate location of an $X$ or $Z$ error prior to the controlled-NOT gate effectively turns it into two errors after the controlled-NOT gate. This happens even when the controlled-NOT gate is perfect, and we must not forget that a given controlled-NOT gate may itself be noisy, which can create correlated errors on two qubits.

Adding to our concern is the fact that subsequent two-qubit gates might propagate these errors even further, as the following figure suggests.

In some sense, we can never get around this; so long as we use multiple-qubit gates, there will be a potential for error propagation. However, as we'll discuss in the subsections that follow, steps can be taken to limit the damage this causes, allowing for propagated errors to be managed.

---

Transversal gate implementations

The simplest known way to mitigate error propagation in fault-tolerant quantum circuits is to implement gates transversally, which means building gadgets for them that have a certain simple form. Specifically, the gadgets must be a tensor product of operations (or, in other words, a depth-one quantum circuit), where each operation can only act on a single qubit position within each code block that it touches. This is perhaps easiest to explain through some examples.

Examples of transversal gate implementations

Consider the following figure, which suggests a transversal implementation of a CNOT gate. (This particular implementation, where CNOTs are performed qubit by qubit, only works for CSS codes — but it does, in fact, work for all CSS codes.)

There are two code blocks in this figure, each depicted as consisting of five qubits (although it could be more, as has already been suggested). The circuit on the right has depth one, and each of the CNOT gates acts on a single qubit position within each block: both the control and target for the first CNOT is the topmost qubit (i.e., qubit 0 using the Qiskit numbering convention), both the control and target for the second CNOT is the qubit second from top (i.e., qubit 1), and so on. Hence, this is a transversal gadget.

For a second example — really a class of examples — consider any Pauli gate. Pauli gates can always be implemented transversally, for any stabilizer code, by building gadgets that are composed of Pauli operations. In particular, every Pauli operation on a logical qubit encoded by a stabilizer code can be implemented transversally by choosing an appropriate Pauli operation on the physical qubits used for the encoding. This is consistent with a fact that was mentioned in passing in the "Stabilizer formalism" lesson: up to a global phase, Pauli operations that commute with every stabilizer generator of a stabilizer code act like Pauli operations on the qubit or qubits encoded by that code.

As a specific example, consider the $9$-qubit Shor code, for which standard basis states could be encoded as follows.

$$\begin{aligned} \vert 0\rangle & \:\mapsto\: \frac{1}{2\sqrt{2}} (\vert 000\rangle + \vert 111\rangle) \otimes (\vert 000\rangle + \vert 111\rangle) \otimes (\vert 000\rangle + \vert 111\rangle) \\[3mm] \vert 1\rangle & \:\mapsto\: \frac{1}{2\sqrt{2}} (\vert 000\rangle - \vert 111\rangle) \otimes (\vert 000\rangle - \vert 111\rangle) \otimes (\vert 000\rangle - \vert 111\rangle) \end{aligned}$$

An $X$ gate on the logical qubit encoded by this code can be implemented transversally by the $9$-qubit Pauli operation

$$Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes \mathbb{I}$$

while a $Z$ gate on the logical qubit can be implemented transversally by the $9$-qubit Pauli operation

$$X \otimes X \otimes X \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}.$$

Both of these Pauli operations have weight $3,$ which is the minimum weight required. (The $9$-qubit Shor code has distance $3,$ so any non-identity Pauli operation of weight $2$ or less is detected as an error.)

And, for a third example, the $7$-qubit Steane code (and indeed every color code) allows for a transversal implementation of all Clifford gates. We've already seen how CNOT gates are implemented transversally for any CSS code, so it remains to consider $H$ and $S$ gates. A Hadamard gate applied to all $7$ qubits of the Steane code is equivalent to $H$ being applied to the logical qubit it encodes, while an $S^{\dagger}$ gate (as opposed to an $S$ gate) applied to all $7$ qubits is equivalent to a logical $S$ gate.

Error propagation for transversal gadgets

Now that we know what transversal implementations of gates are, let us discuss their connection to error propagation.

For a transversal implementation of a single-qubit gate, we simply have a tensor product of single-qubit gates in our gadget, which acts on a code block of physical qubits for the chosen quantum error correcting code. Although any of these gates could fail and introduce an error, there will be no propagation of errors because no multiple-qubit gates are involved. Immediately after the gadget is applied, error correction is performed; and if the number of errors introduced by the gadget (or while the gadget is being performed) is sufficiently small, the errors will be corrected. So, if the rate of errors introduced by faulty gates is sufficiently small, error correction has a good chance to succeed.

For a transversal implementation of a two-qubit gate, on the other hand, there is the potential for a propagation of errors — there is simply no way to avoid this, as we have already observed. The essential point, however, is that a transversal gadget can never cause a propagation of errors within a single code block.

For example, considering the transversal implementation of a CNOT gate for a CSS code described above, an $X$ error could occur on the top qubit of the top code block right before the gadget is performed, and the first CNOT within the gadget will propagate that error to the top qubit in the lower block. However, the two resulting errors are now in separate code blocks. So, assuming our code can correct an $X$ error, the error correction steps that take place after the gadget will correct the two $X$ errors individually — because only a single error occurs within each code block. In contrast, if error propagation were to happen inside of the same code block, it could turn a low-weight error into a high-weight error that the code cannot handle.

Non-universality of transversal gates

For two different stabilizer codes, it may be that a particular gate can be implemented transversally with one code but not the other. For example, while it is not possible to implement a $T$ gate transversally using the $7$-qubit Steane code, there are other codes for which this is possible.

Unfortunately, it is never possible, for any non-trivial quantum error correcting code, to implement a universal set of gates transversally. This fact is known as the Eastin-Knill theorem.

Theorem (Eastin-Knill). For any quantum error correcting code with distance at least 2, the set of logical gates that can be implemented transversally generates a set of operations that (up to a global phase) is discrete, and is therefore not universal.

The proof of this theorem will not be explained here. (It is not a complicated proof, but it does require a basic knowledge of Lie groups and Lie algebras, which are not among the series prerequisites.) The basic idea, however, can be conveyed in intuitive terms: Infinite families of transversal operations can't possibly stay within the code space of a non-trivial code because minuscule differences in transversal operations are well-approximated by low-weight Pauli operations, which the code detects as errors.

In summary, transversal gadgets offer a simple and inherently fault-tolerant implementation of gates — but for any reasonable choice of a quantum error correcting code, there will never be a universal gate set that can be implemented in this way, which necessitates the use of alternative gadgets.

---

Magic states

Given that it is not possible, for any non-trivial choice for a quantum error correcting code, to implement a universal set of quantum gates transversally, we must consider other methods to implement gates fault-tolerantly. One well-known method is based on the notion of magic states, which are quantum states of qubits that enable fault-tolerant implementations of certain gates.

Implementing gates with magic states

Let us begin by considering $S$ and $T$ gates, which have matrix descriptions as follows.

$$S = \begin{pmatrix} 1 & 0\\ 0 & i \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & e^{i\pi/2} \end{pmatrix} \qquad\text{and}\qquad T = \begin{pmatrix} 1 & 0\\ 0 & \frac{1+i}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & e^{i\pi/4} \end{pmatrix}$$

By definition, $S$ is a Clifford operation, while $T$ is not; it is not possible to implement a $T$ gate with a circuit composed of Clifford gates ($H$ gates, $S$ gates, and CNOT gates).

However, it is possible to implement a $T$ gate (up to a global phase) with a circuit composed of Clifford gates if, in addition, we have a copy of the state

$$T\vert {+} \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{e^{i\pi/4}}{\sqrt{2}} \vert 1\rangle,$$

and we allow for standard basis measurements and for gates to be classically controlled. In particular, the following circuit shows one way to do this. The phenomenon on display here is a somewhat simplified example of quantum gate teleportation.

To check that this circuit works correctly, we can first compute the action of the CNOT gate on the input.

$$T \vert {+} \rangle \otimes \vert\psi\rangle \stackrel{\text{CNOT}}{\longmapsto} \frac{1}{\sqrt{2}} \vert 0\rangle \otimes T \vert \psi\rangle + \frac{1+i}{2} \vert 1\rangle \otimes T^{\dagger} \vert \psi\rangle$$

The measurement therefore gives the outcomes $0$ and $1$ with equal probability. If the outcome is $0,$ the $S$ gate is not performed, and the output state is $T\vert\psi\rangle;$ and if the outcome is $1,$ the $S$ gate is performed, and the output state is $ST^{\dagger}\vert\psi\rangle = T\vert \psi\rangle.$

The state $T\vert {+}\rangle$ is called a magic state in this context, although it's not unique in this regard: other states are also called magic states when they can be used in a similar way (for possibly different gates and using different circuits). For example, exchanging the state $T\vert{+}\rangle$ for the state $S\vert{+}\rangle$ and replacing the $S$ gate in the circuit above with a $Z$ gate implements an $S$ gate — which is potentially useful for fault-tolerant quantum computation using a code for which $S$ gates cannot be implemented transversally.

Fault-tolerant gadgets from magic states

It may not be clear that using magic states to implement gates is helpful for fault-tolerance. For the $T$ gate implementation described above, for instance, it appears that we still need to apply a $T$ gate to a $\vert{+}\rangle$ state to obtain a magic state, which we then use to implement a $T$ gate. So what is the advantage of using this approach for fault-tolerance?

Here are three key points that provide an answer to this question.

1. The creation of magic states does not necessitate applying the gate we're attempting to implement to a particular state. For example, applying a $T$ gate to a $\vert {+} \rangle$ state is not the only way to obtain a $T\vert{+}\rangle$ state.

2. The creation of magic states can be done separately from the computation in which they're used. This means that errors that arise in the magic state creation process will not propagate to the actual computation being performed.

3. If the individual gates in the circuit implementing a chosen gate using a magic state can be implemented fault-tolerantly, and we assume the availability of magic states, we obtain a fault-tolerant implementation of the chosen gate.

To simplify the discussion that follows, let's focus in on $T$ gates specifically — keeping in mind that the methodology can be extended to other gates. A fault-tolerant implementation of a $T$ gate using magic states takes the form suggested by the following figure.

Qubits in the original $T$-gate circuit correspond to logical qubits in this diagram, which are encoded by whatever code we're using for fault-tolerance. The inputs and outputs in the diagram should therefore be understood as encodings of these states. This means, in particular, that we actually don't need just magic states — we need encoded magic states. The gates in the original $T$-gate circuit are here replaced by gadgets, which we assume are fault-tolerant.

This particular figure therefore suggests that we already have fault-tolerant gadgets for CNOT gates and $S$ gates. For a color code, these gadgets could be transversal; for a surface code (or any other CSS code), the CNOT can be performed transversally, while the $S$ gate gadget might itself be implemented using magic states, as was earlier suggested is possible. (The figure also suggests that we have a fault-tolerant gadget for performing a standard basis measurement, which we've ignored thus far. This could actually be challenging for some codes selected to make it so, but for a CSS code it's a matter of measuring each physical qubit followed by classical post-processing.)

The implementation is therefore fault-tolerant, assuming we have an encoding of a magic state $T\vert{+}\rangle.$ But, we still haven't addressed the issue of how we obtain an encoding of this state. One way to obtain encoded magic states (or, perhaps more accurately, to make them better) is through a process known as magic state distillation. The following diagram illustrates what this process looks like at the highest level.

In words, a collection of noisy encoded magic states is fed into a special type of circuit known as a distiller. All but one of the output blocks is measured — meaning that logical qubits are measured with standard basis measurements. If any of the measurement outcomes is $1,$ the process has failed and must be restarted. If, however, every measurement outcome is $0,$ the resulting state of the top code block will be a less noisy encoded magic state. This state could then join four more as inputs into another distiller, or used to implement a $T$ gate if it is deemed to be sufficiently close to a true encoded magic state. Of course, the process must begin somewhere, with one possibility being to prepare them non-fault-tolerantly.

There are different known ways to build the distiller itself, but they will not be explained or analyzed here. At a logical level, the typical approach — remarkably and somewhat coincidentally — is to run an encoding circuit for a stabilizer code in reverse! This could, in fact, be a different stabilizer code from the one used for error correction. For example, one could potentially use a surface or color code for error correction, but run an encoder for the $5$-qubit code in reverse for the sake of magic state distillation. Encoding circuits for stabilizer codes only require Clifford gates, which simplifies the fault-tolerant implementation of a distiller. In actuality, the specifics are dependent on the codes that are used.

In summary, this section has aimed to provide only a very high-level discussion of magic states, with the intention being to provide just a basic idea of how it works. It is sometimes claimed that the overhead for using magic states to implement gates fault-tolerantly along these lines would be extremely high, with the vast majority of the work going into the distillation process. However, this is actually not so clear — there are many potential ways to optimize these processes. There are, in addition, alternative approaches to building fault-tolerant gadgets for gates that cannot be implemented transversally. For example, code deformation and code switching are keywords associated with some of these schemes — and new ways continue to be developed and refined.

---

Fault-tolerant error correction

In addition to the implementation of the various gadgets required for a fault-tolerant implementation of a given quantum circuit, there is another important issue that must be recognized: the implementation of the error correction steps themselves. This goes back to the idea that anything involving quantum information is susceptible to errors — including the circuits that are themselves meant to correct errors.

Consider, for instance, the type of circuit described in "The stabilizer formalism" lesson for measuring stabilizer generators non-destructively using phase estimation. These circuits are clearly not fault-tolerant because they can cause errors to propagate within the code block on which they operate. This might seem rather problematic, but there are multiple known ways to perform error correction fault-tolerantly in a way that does not cause errors to propagate within the code blocks being corrected.

One method is known as Shor error correction, because it was first discovered by Peter Shor. The idea is to perform syndrome measurements using a so-called cat state, which is an $n$-qubit state of the form

$$\frac{1}{\sqrt{2}} \vert 0^n \rangle + \frac{1}{\sqrt{2}} \vert 1^n \rangle,$$

where $0^n$ and $1^n$ refer to the all-zero and all-one strings of length $n.$ For instance, this is a $\vert\phi^+\rangle$ state when $n=2$ and a GHZ state when $n=3,$ but in general, Shor error correction requires a state like this for $n$ being the weight of the stabilizer generator being measured.

As an example, the circuit shown here measures a stabilizer generator of the form $P_2\otimes P_1 \otimes P_0.$

This necessitates the construction of the cat state itself, and to make it work reliably in the presence of errors and potentially faulty gates, the method actually requires repeatedly running circuits like this to make inferences about where different errors may have occurred during the process.

An alternative method is known as Steane error correction. This method works differently, and it only works for CSS codes. The idea is that we don't actually perform the syndrome measurements on the encoded quantum states in the circuit we're trying to run, but instead we intentionally propagate errors to a workspace system, and then measure that system and classically detect errors. The following circuit diagrams illustrate how this can be done for detecting $X$ and $Z$ errors, respectively.

A related method known as Knill error correction extends this method to arbitrary stabilizer codes using teleportation.