Chapter 10 - Fault-Tolerant Quantum Computing

Introduction

As the name implies, fault-tolerant quantum computing means that quantum computations can be performed in spite of errors in the computation. To ensure that a computation is reliable, one must be able to prevent errors from accumulating. This could happen, for example, if a small error occurs on one qubit and propagates to many others before it is fixed. What are all the ways in which an error can occur and how can they be prevented from accumulating to produce erroneous results? In this chapter, these questions are addressed.

Requirements for Fault-Tolerance

As Preskill puts it in Lo, Popescu, and Spiller [26], one needs to "...sniff out all the ways in which a recovery failure could result from a single error, ..." Then, in a Proc. Roy. Soc. London article [34], he gives five laws for reliable quantum computing, as he reviews the results obtained for avoiding failure. Here, a slightly modified list is discussed. The list is

1. Be careful not to propagate errors,
2. Copy errors not data,
3. Carefully prepare ancilla,
4. Verify ancilla,
5. Verify the syndrome,
6. Take care with measurements.

All of these require some explanation. Let us take them in order.

1. Propagation of Errors

The general statement is that an error should not propagate within a code block and errors should not accumulate. If there is an error probability of $\epsilon \,\!$ for one physical qubit, then the objective is to ensure that the block error is reduced by a power. For protection against one error, the block error should be $\epsilon ^{2}\,\!$, and when encoding against $t\,\!$ errors, the block error should be $\epsilon ^{t+1}\,\!$. If an error propagates within a block, the block error becomes $\epsilon \,\!$ and the encoding has lost all its benefit.

For example, one should be careful when qubits are reused because error correction procedures can actually propagate errors. Consider the syndrome measurement in Figure 7.2. In that circuit, one of the ancillary qubits is used twice to check the parity of a pair of qubits in the bit-flip code. This, however, can propagate a single error in the ancilla to two qubits in the code block. However, this code can only detect and correct one error. Thus such an event would lead to failure.

Figure 10.1

Figure 10.1: This circuit is not fault-tolerant. It is the same as Figure 7.2. Figure Figure 10.2 below is fault-tolerant.

Figure 10.2

Figure 10.2: The circuit is fault-tolerant. However, as explained in the text, it cannot be used.

At first this may not seem likely. After all, the target bit is the one that is affected. However, as shown in Figure 10.3 errors can actually propagate from the target to the source, not just from the source to the target, in the CNOT operation.

Figure 10.3

Figure 10.3: The above circuit identity was used by Preskill to show that errors can propagate in not-so-obvious ways. In this particular case, an error can propagate from the source qubit as well as propagating to the target qubit in a CNOT gate.

2. Copy Errors Not Data

One ancilla for each physical qubit in the encoded block gives too much information about the state. If there is one ancilla for each qubit and all are measured, the superposition of $\alpha \,\!$ and $\beta \,\!$ will be destroyed. This is because the information obtained will result in a $|000\rangle \,\!$ or $|111\rangle \,\!$ state of the system. The data, not just the error, has been extracted leaving only classical information. This is clearly unacceptable for quantum information where the details of the state must never be revealed during the computation. Therefore, another method for ancilla preparation and syndrome extraction must be used.

3. Carefully Prepare the Ancilla

In the previous section, the fault-tolerant method extracted too much information. So what can be done? The answer is that a different recovery procedure should be used. Rather than using single qubit ancilla, the ancillary system can composed of several qubits in a special state.

Here are two examples for the Steane code.

1) Shor proposed state (one example of the special preparation of an ancilla state which is the superposition of all even weighted strings);

	$|{\mbox{Shor}}\rangle _{\text{anc}}={\frac {1}{\sqrt {8}}}\sum _{{\text{even }}v}|v\rangle _{\text{anc}}.\,\!$	(10.1)

In this case, one computes the syndrome by performing four CNOT gates and then measure the ancilla state. Since the ancilla state is a superposition of all even weighted states, the result will project onto an even weighted string if there is no error and a superposition of odd weight states if there is an error. Thus giving the syndrome information. The parity of the ancillary system indicates whether or not there is an error, but without revealing the state of the system.

The second example was given by Steane. The ancilla state is given by;

	$|{\text{Steane}}\rangle _{\text{anc}}={\frac {1}{\sqrt {4}}}\sum _{\text{Hamming}}|v\rangle _{\text{anc}}.\,\!$	(10.2)

In this case the ancilla are measured directly and the classical Hamming code is used to diagnose the errors using the parity check matrix for the classical code.

The differences between the two are as follows:

Shor: 6 syndrome bits, 24 ancilla, 24 CNOT gates

Steane: 14 ancilla, 14 CNOT, the ancilla state is more difficult to prepare.

4. Verifying the Ancilla

Since the ancilla is so important, and can propagate an error to the logical qubit (encoded block), it must be carefully prepared and checked for errors. If there is an error, the ancilla must be thrown away and another ancilla prepared. This must be repeated until the probability for error in the ancilla is sufficiently low.

5. Check the Measurement

Checking the measurement, by measuring more than once for each example, is necessary since error correction during the computation is not useful if the output of the computation is flawed.

Concatenated Codes

Concatenating a code means that a quantum error correcting code is used to encode the set of qubits in a code. That is, each qubit in a code is also an encoded qubit. One can continue so that the next set of qubits is also a set of encoded qubits. So, for example, in the bit-flip code, one would use three qubits to encode one logical one. But if each of the qubits used in the encoding is also an encoded qubit, using three qubits, then there are a total of 9. Continuing will lead to a code which uses $L\,\!$ levels of encoding, using $n\,\!$ qubits, say, which will produce a total overhead of $n^{L}\,\!$ qubits to encode one logical one.

There are several advantages to this. One, the measurement and recovery can (in principle) be carried out in parallel for the different levels. Thus error correction can be performed more efficiently than if the code were simply to be encoded using more qubits in each block. (In other words, simply increasing the distance can increase the error correction recovery procedure.)

Two, due to this, the scaling of the gate error rate it better. The gates do not need to be implemented in sequence and the error probability can be reduced, assuming the error rate per elementary (physical) gate is low enough.

Fault-Tolerant Quantum Computing for the Steane Code

Once a code is concatenated, gates will need to be performed.

Gates that can be performed bit-wise:

$H,X,CNOT,P\,\!$, where

$P=\left({\begin{array}{cc}1&0\\0&i\end{array}}\right)\,\!$

However, these are not universal. So they need to be supplemented with another gate.

Solution: Prepare an ancilla state, check it, and use it to implement a gate using gates from the fault-tolerant set.

This sets up a timing problem. How can the ancilla state be prepared at the right time since it is thrown out if it is bad? One cannot wait until it is needed to prepare it. If one did wait, the original state is stored while this one is created.

$\,\!$