18 Fault-tolerant computation

Error correcting codes are effective for storage and transfer of data. However, they are not directly suitable for continuous computation. In this context two problems arises:

How to apply an operation on logical qubits? For example, suppose we want to apply a Hadamard-gate to a logical qubit encoded using Shor’s code. A naive approach would be to decode the nine physical qubits back to obtain a single logical qubit, apply the Hadamard-gate, and then encode back to the nine physical qubits: \[ \xrightarrow{\text{\large decode}} \xrightarrow{\text{\large operation}} \xrightarrow{\text{\large encode}}. \] This is problematic because errors may occur between encoding and decoding. The error correcting code cannot protect against this. Therefore, we must find another to apply operations directly on the encoded logical qubit.
Even if we solve the first problem: The new operations (which may be more complex) could themselves introduce errors – maybe too many to correct.

18.1 Operations on logical/physical qubits

We begin by solving the first problem: Performing an operation directly on the encoded qubit without decoding and encoding again.

Let us recall Shor’s code. We write the encoded qubit \(\ket{0}\) as \(\ket{\tilde{0}}\) and the encoded qubit \(\ket{1}\) as \(\ket{\tilde{1}}\). Suppose we want to apply an \(X\)-gate to the logical qubit, i.e. construct an operation \(\tilde{X}\) that acts on the nine physical qubits such that: \[ \begin{aligned} \tilde{X}: \ket{\tilde{0}} &\mapsto \ket{\tilde{1}}, \\ \tilde{X}: \ket{\tilde{1}} &\mapsto \ket{\tilde{0}}. \end{aligned} \]

This is possible by applying \(Z\) to the first qubit on each block (i.e. physical qubits 1, 4 and 7) or applying \(Z\) to all nine physical qubits. Similarly the operation \(\tilde{Z}\) works also by applying \(X^{\otimes 9}\). We call such easily to implement gates transversal:

Definition 18.1 (Transversal gate) A gate is called transversal if it can be implemented by applying identical gates to each physical qubit separately.

(Note that there are slightly different definitions of “transversal”. Some only call a gate \(G\) transversal if it can be implemented by applying \(G\) to each qubit.)

However, this method does not work for all unitaries. For example, the Hadamard-gate \(H\) cannot be implemented on Shor’s code as \(\tilde{H}\) in such a simple way.

A better alternative is the Steane code, which encodes a logical qubit into seven physical qubits and can correct one error (see Section 17.3).

For each gate \(G \in \{Y, X, Z\}\) the logical operation \(G\) is implemented as the physical operation \(\tilde{G} = G^{\otimes 7}\). And \(S\) is implemented by \(S^{\otimes 7}\) followed by \(Z^{\otimes 7}\). Similarly, the logical \(\widetilde{\mathit{CNOT}}\)-gate can be implemented using seven \(\mathit{CNOT}\)-gates. Thus these gates are all transversal.

As shown in Section 16.4 in the previous chapter, these gates alone do not form a universal set of gates. However, if the physical \(\tilde{T}\)-gate can also be implemented, we achieve a universal set of gates (see Theorem 16.4).

Unfortunately, the \(T\)-gate is not transversal. And we know from Section 16.4 and Theorem 16.4 that we need \(T\) to get a universal set of gates. Nevertheless, it is known that a more complex method exists to implement \(\tilde{T}\) on the Steane code. (We omit the details here.)

Conclusion: With the Steane code, it is possible to implement all quantum circuits on encoded qubits without decoding and encoding again.

18.2 Fault-tolerant gates

While the Steane code solves the first problem, we now look at the second problem: We need to compute on encoded qubits using physical gates with an error probability \(p\) such that error probability per logical gate is \(\ll p\); ideally arbitrary small.

In the following, we will focus on applying unitaries and will ignore initialization and measurement.

To solve the problem, two ingredients are necessary:

A quantum error correcting code for one logical qubit, capable of correcting one error (e.g., the Steane code).
A “fault-tolerant implementation” of logical gates. The definition follows.

Let us examine the following circuit:

Example situation for fault-tolerance to apply

To make this circuit fault-tolerant, we replace it with:

In this transformation:

Each physical qubit is encoded as a block of qubits using a quantum error correcting code (e.g., the Steane code).
Each gate is replaced by a fault-tolerant implementation (e.g., \(H\) by fault-tolerant (FT) \(H\)).
An error correction step is added after each gate.

For this construction to work, the following three requirements must be satisfied:

For each fault-tolerant gate implementation: If there is at most one physical error in the inputs, then there is at most one physical error per output block. (Transversal gates satisfy this automatically.)
For each fault-tolerant gate implementation: If the input contains no error and at most one physical gate error occurs, then there is at most one physical error per output block. (Transversal gates satisfy this automatically.)
For each error correction procedure: If there is no error in the inputs and at most one error occurred, then there is at most one error in the output.

18.2.1 Analysis of a circuit

Let us as analyze the following circuit for \(\mathit{CNOT}\) (an analogous analysis works for other gates and gives the same result):

For the analysis we make three assumptions:

Each physical gate has an error probability of \(p\) (i.e., with probability \(p\), the gate does some thing arbitrary; with probability \(1-p\) it does what it is supposed to).
All errors occur independently.
The circuit satisfies the three requirements for fault-tolerance listed above.

Let \(G\) be the number of physical gates used in this circuit.

We will now analyze what errors got introduced by this gate with what probabilities:

Position 1 (before the FT CNOT):

\(P_1\): Probability that exactly one error is present (in all blocks together).
\(P_2\): Probability that at least two errors are present.

Position 2 (after the FT CNOT):

\(P_1'\): Probability of at most one error per block (but at least on error in total). This can occur in three ways:

No error before the FT CNOT, and an error occurred during the FT CNOT: Probability of this is \(\leq G \cdot p\).
One error already existed before the FT CNOT (probability \(P_1\)), and no additional error occurred during FT CNOT: Probability of this is \(\leq P_1\).
Also, it could happen that there were at least two errors, and we “accidentally” correct some. We ignore this case because those cases will be counted in the case (\(P_2'\)) anyway and a \(100\%\) correct formulation would be very complicated.

So: \[ P_1' \leq Gp + P_1. \]

\(P_2'\): Probability of at least two errors in at least one block. This can occur in five ways:

No error before the gate, and a single error during the gate: Cannot lead to two errors by (B).
No error before the gate, but at least two errors during the gate: Probability of this is \(\leq (Gp)^2\).
One error before the gate, and no error during the gate: Cannot lead to two errors by (A).
One error on the input of the gate, and one during the gate: Probability of this is \(\leq P_1 \cdot Gp\).
At least two errors before the gate: Probability of this is \(\leq P_2\).

So: \[ P_2' \leq (Gp)^2 \quad + \quad P_1 \cdot Gp \quad + \quad P_2. \]

Position 3 (after the error correction):

\(P_1''\): Probability of exactly one error. This can occur in one way:

No error at position 2, but one error happens during error correction: Probability of this is \(\leq Gp\).

So: \[ P_1'' \leq Gp. \]

\(P_2''\): Probability of at least two errors. This can occur in five ways:

No error at position 2, and one error occurs during the correction: Cannot lead to two errors by (C).
No error at position 2, but at least two errors occur during the correction: Probability of this is \(\leq (Gp)^2\).
One error at position 2, and no error occurs during the correction: Does not happen because the code corrects one error.
At most one error per block at position 2, and at least one error occurs during the correction: Probability of this is \(\leq P_1' \cdot Gp \leq (P_1 + Gp) \cdot Gp = P_1 \cdot Gp + (Gp)^2\).
Two or more errors at position 2: Probability of this is \(\leq P_2' \leq (Gp)^2 + P_1 \cdot Gp + P_2\).

So: \[ P_2'' \leq (Gp)^2 \quad + \quad P_1 \cdot Gp + (Gp)^2 \quad + \quad (Gp)^2 + P_1 \cdot Gp + P_2. \]

If we additionally assums \(P_1 \leq Gp\), we have: \[ P_2'' \leq 5 \cdot (Gp)^2 + P_2. \]

At the beginning of a large circuit consisting of \(l\) fault-tolerant implemented gates, we have \(P_1 = 0 \leq Gp\), and thus by induction, we have \(P_2'' \leq 5 \cdot (Gp)^2 + P_2\) after each fault-tolerant implemented gate. So the final \(P_2''\) will be \(\leq l \cdot 5 \cdot (Gp)^2\). So per fault-tolerant gate, we have a probability of \(\leq 5 \cdot (Gp)^2 + P_2\) of introducing an uncorrectable error.

18.2.2 Development of the error probability

So \(P_2\) increases by \((Gp)^2\) per logical gate. So for a \(p\)-error physical gate, we get a \(5(Gp)^2\)-error logical gate assuming one correctable error in the output is acceptable.

For some nontrivial, but not arbitrary small \(p\), it is \(5(Gp)^2 < p\).

Let try an example with \(G = 50\) and \(p = \frac{1}{10 000}\): \[ 5(Gp)^2 = \frac{5 \cdot 50^2}{10 000^2} = \frac{1}{8 000}. \] In this case the logical error is higher than the physical one, so the fault-tolerance fails. Now let change the example to \(p = \frac{1}{15000}\): \[ 5(Gp)^2 = \frac{5 \cdot 50^2}{15 000^2} = \frac{1}{18 000}. \] Now the logical error is lower, so the fault-tolerance works.

One easily sees that whenever \(p < \frac{1}{5 G^2}\), the error will be reduced.

Reducing the error arbitrarily:

Using an fault-tolerant implementation as described above, we can construct a quantum computer with logical error probability \(p_{i+1} < p_i\) from a quantum computer with error probability \(p_i\), as long as \(p_i < \frac{1}{5 G^2}\). But that means that if we start with a quantum computer with logical error probability \(p_1 < \frac{1}{5 G^2}\), we can construct one with logical error probability \(p_2\), and based on that with logical error probability \(p_3\) (adding one more layer of fault-tolerant computation), and from that with logical error probability \(p_4\) and so on. And \(p_1 > p_2 > p_3 > p_4 > \dots\) (and a slightly more careful analysis shows that the error drops fast).

This leads us to the following theorem:

Theorem 18.1 (Threshold theorem) If the physical gate error rate is below a certain threshold, then the logical error rate can be made arbitrary small using fault-tolerant quantum computation.

The threshold (here \(\frac{1}{5 G^2}\)) is believed to lie between \(0.1\%\) and \(1\%\) in reality.