Fault-tolerant quantum computation

Open the YouTube video for this lesson in a separate window.

Introduction

In the previous lessons of this course, we've seen several examples of quantum error correcting codes, which can detect and allow for the correction of errors — so long as not too many qubits are affected. If we want to use error correction for quantum computing, however, there are still many issues to be reckoned with. This includes the reality that not only is quantum information fragile and susceptible to noise, but the quantum gates, measurements, and state initializations used to implement quantum computations will themselves be imperfect.

For instance, if we wish to perform error correction on one or more qubits that have been encoded using a quantum error correcting code, then this must be done using gates and measurements that might not work correctly — which means not only failing to detect or correct errors, but possibly introducing new errors. In addition, the actual computations we're interested in performing must be implemented, again with gates that aren't perfect. But we certainly can't risk decoding qubits for the sake of performing these computations, and then re-encoding once we're done, because errors might strike when the protection of a quantum error correcting code is absent. This means that quantum gates must somehow be performed on logical qubits that never go without the protection of a quantum error correcting code.

This all presents a major challenge. But it is known that, as long as the level of noise falls below a certain threshold value, it is possible in theory to perform arbitrarily large quantum computations reliably using noisy hardware. We'll discuss this critically important fact, which is known as the threshold theorem, toward the end of the lesson.

The lesson starts with a basic framework for fault-tolerant quantum computing, including a short discussion of noise models and a general methodology for fault tolerant implementations of quantum circuits. We'll then move on to the issue of error propagation in fault-tolerant quantum circuits and how to control it. In particular, we'll discuss transversal implementations of gates, which offer a very simple way to control error propagation — though there is a fundamental limitation that prevents us from using this method exclusively — and we'll also take a look at a different methodology involving so-called magic states, which offers a different path to controlling error propagation in fault-tolerant quantum circuits.

And finally, the lesson concludes with a high-level discussion of the threshold theorem, which states that arbitrarily large quantum circuits can be implemented reliably, so long as the error rate for all of the components involved falls below a certain finite threshold value. This threshold value depends on the error correcting code that is used, as well as the specific choices that are made for fault-tolerant implementations of gates and measurements, but critically it does not depend on the size of the quantum circuit being implemented.

An approach to fault tolerance

We'll begin by outlining a basic approach to fault-tolerant quantum computing based on quantum circuits and error correcting codes. For the sake of this discussion, let us consider the following example of a quantum circuit. This happens to be a teleportation circuit, including the preparation of the e-bit, but the specific functionality of the circuit is immaterial — it's just an example, and in actuality we're likely to be interested in significantly larger circuits.

A teleportation circuit

A circuit like this one represents an ideal, and an actual implementation of it won't be perfect. So what could go wrong?

The fact of the matter is that quite a lot could go wrong! In particular, the state initializations, unitary operations, and measurements will all be imperfect; and the qubits themselves will be susceptible to noise, including decoherence, at every point in the computation, even when no operations are being performed on them and they're simply storing quantum information. That is to say, just about everything could go wrong.

There is one exception, though: Any classical computations that are involved are assumed to be perfect — because, practically speaking, classical computations are perfect. For example, if we decide to use a surface code for error correction, and a classical perfect matching algorithm is run to compute corrections, we really don't need to concern ourselves with the possibility that errors in this classical computation will lead to a faulty solution. As another example, quantum computations often necessitate classical pre- and post-processing, and these classical computations can safely be assumed to be perfect as well.

Noise models

To analyze fault-tolerant implementations of quantum circuits, we require a precise mathematical model — a noise model — through which probabilities for various things to go wrong can be associated. Hypothetically speaking, one could attempt to come up with a highly detailed, complicated noise model that aims to reflect the reality of what happens in a particular device. But, if the noise model is too complicated or difficult to reason about, it will likely be of limited use. For this reason, simpler noise models are much more typically considered.

One example of a simple noise model is the independent stochastic noise model, where errors or faults affecting different components at different moments in time — or, in other words, different locations in a quantum circuit — are assumed to be independent. For instance, each gate might fail with a certain probability, an error might strike each stored qubit with a different probability per unit time, and so on, with no correlations among the different possible errors.

Now, it is certainly reasonable to object to such a model, because there probably will be correlations among errors in real physical devices. For instance, there might be a small chance of a catastrophic error that wipes out all the qubits at once. Perhaps more likely, there could be errors that are localized but that nevertheless affect multiple components in a quantum computer. Nobody suggests otherwise! Nevertheless, the independent stochastic noise model does provide a simple baseline that captures the idea that nature is unpredictable but not malicious, and it isn't intentionally trying to ruin quantum computations.

Other, less forgiving noise models are also commonly studied. For example, a common relaxation of the assumption of independence among errors affecting different locations in a quantum circuit is that just the locations of the errors are independent, but the actual errors affecting these locations could be correlated. Regardless of what noise model is chosen, it should be recognized that learning about the errors that affect specific devices, and formulating new error models if the old ones lead us astray, could potentially be an important part of the development of fault-tolerant quantum computation.

Fault-tolerant circuit implementations

Next we'll consider a basic strategy for fault-tolerant implementations of quantum circuits. We'll use the teleportation circuit above as a running example to illustrate the strategy, though it could be applied to any quantum circuit.

Here's a diagram of a fault-tolerant implementation of our teleportation circuit.

Fault-tolerant implementation of a teleportation circuit

The individual components in this diagram and their connection to the original circuit are as follows.

State preparations, unitary gates, and measurements are not performed directly, as single operations, but rather are performed by so-called gadgets, which could each involve multiple qubits and multiple operations. In the diagram, gadgets are indicated by purple boxes labelled by whatever state preparation, gate, or measurement is to be implemented.
The logical qubits on which the original, ideal circuit is run are protected using a quantum error correcting code. Rather than acting directly on these logical qubits, the gadgets act on the physical qubits that encode them. The diagram suggests that 5 physical qubits are used for each logical qubit, as if the $5$ -qubit code were being used, but the number could naturally be different. It is worth stressing that these logical qubits are never exposed — they spend their entire existence being protected by whatever quantum error correcting code we've chosen.
Error correction is performed repeatedly, as suggested by the blue boxes labeled EC in the diagram, throughout the computation. It is critically important that this is done both frequently and in parallel. As errors take place, builds up, and constant work is required to remove it from the system at a high enough rate to allow the computation to function correctly.

There are therefore some specific choices that must be made, including the selection of the gadgets as well as the quantum error correcting code itself. Once these choices have been made, and assuming a particular noise model has been adopted, there is a fundamental question that we may ask ourselves: Is this actually helping? That is, are we making things better, or might we actually be making things worse?

If the rate of noise is too high, the entire process just suggested could very well be making things worse, just like the 9-qubit Shor code makes things worse for independent errors if the error probability on each qubit is above the break-even point. If, however, the rate of noise is below a certain threshold, then all of this extra work will get us somewhere — and as we'll discuss toward the end of the lesson, paths open up for further reduction of the error.

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.

Circuit representations of error propagation by CNOT gates

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 as a result.

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

Circuit representations of error propagation by multiple CNOT gates

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.)

Transversal implementation of a CNOT gate

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 operation 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 be 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 happens on 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 (as we already observed in the Stabilizer formalism lesson); 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.

A circuit diagram depicting magic state injection

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.

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.
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.
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.

A circuit diagram depicting magic state injection on an encoded qubit

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.

A circuit diagram representing distillation of encoded magic states

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 than 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. As we know from the lesson on the stabilizer formalism, 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 lesson on the stabilizer formalism 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 works for measuring a stabilizer generator of the form $P_2\otimes P_1 \otimes P_0.$

A Shor error detection circuit

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, which was first proposed by Andrew Steane. 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 Steane error detection circuit

A related method known as Knill error correction, first proposed by Manny Knill, extends this method to arbitrary stabilizer codes using teleportation.

Threshold theorem

The final topic of discussion for the lesson is a very important theorem known as the threshold theorem. Here is a somewhat informal statement of this theorem.

Theorem (The threshold theorem). A quantum circuit having size $N$ can be implemented with high accuracy by a noisy quantum circuit, provided that the probability of error at each location in the noisy circuit is below a fixed, nonzero threshold value $p_{\text{th}} > 0.$ The size of the noisy circuit scales as $O(N \log^c(N))$ for a positive constant $c.$

In simple terms, it says that if we have any quantum circuit having $N$ gates, where $N$ can be as large as we like, then it's possible to implement that circuit with high accuracy using a noisy quantum circuit, provided that the level of noise is below a certain threshold value that is independent of N. Moreover, it isn't too expensive to do this, in the sense that the size of the noisy circuit required is on the order of $N$ times some constant power of the logarithm of $N.$

To state the theorem more formally requires being specific about the noise model, which will not be done in this lesson. It can, for instance, be proved for the independent stochastic noise model that was mentioned earlier, where errors occur independently at each possible location in the circuit with some probability strictly smaller than the threshold value, but it can also be proved for more general noise models where there can be correlations among errors.

This is a theoretical result, and the most typical way it is proved doesn't necessarily translate to a practical approach, but it does nevertheless have great practical importance. In particular, it establishes that there is no fundamental barrier to performing quantum computations using noisy components; as long as the error rate for these components is below the threshold value, they can be used to build reliable quantum circuits of arbitrary size. An alternative way to state its importance is to observe that, if the theorem wasn't true, it would be hard to imagine large-scale quantum computing ever becoming a reality.

There are many technical details involved in formal proofs of (formal statements of) this theorem, and those details will not be communicated here — but the essential ideas can nevertheless be explained at an intuitive level. To make this explanation as simple as possible, let's imagine that we use the $7$ -qubit Steane code for error correction. This would be an impractical choice for an actual physical implementation — as would be reflected by a minuscule threshold value $p_{\text{th}}$ — but it works well to convey the main ideas. This explanation will also be rather cavalier about the noise model, with the assumption being that an error strikes each location in a fault-tolerant implementation independently with probability $p.$

Now, if the probability $p$ is larger than the reciprocal of $N,$ the size of the circuit we aim to implement, chances are very good that an error will strike somewhere. So, we can attempt to run a fault-tolerant implementation of this circuit, following the prescription outlined in the lesson. We may then ask ourselves the question suggested earlier: Is this making things better or worse?

If the probability $p$ of an error at each location is too large, then our efforts will not help and may even make things worse, just like the $9$ -qubit Shor code doesn't help if the error probability is above 3.23% or so. In particular, the fault-tolerant implementation is considerably larger than our original circuit, so there are a lot more locations where errors could strike.

However, if $p$ is small enough, then we will succeed in reducing the error probability for the logical computation we're performing. (In a formal proof, we would need to be very careful at this point: errors in the logical computation will not necessarily be accurately described by the original noise model. This, in fact, motivates less forgiving noise models where errors might not be independent — but we will sweep this detail under the rug for the sake of this explanation.)

In greater detail, in order for a logical error to occur in the original circuit, at least two errors must fall into the same code block in the fault-tolerant implementation, given that the Steane code can correct any single error in a code block. Keeping in mind there are many different ways to have two or more errors in the same code block, it is possible to argue that the probability of a logical error at each location in the original circuit is at most $C p^2$ for some fixed positive integer $C$ that depends on the code and the gadgets we use, but critically not on $N,$ the size of the original circuit. If $p$ is smaller than $1/C,$ which is the number we can take as our threshold value $p_{\text{th}},$ this translates to a reduction in error.

However, this new error rate might still be too high to allow the entire circuit to work correctly. A natural thing to do at this point is to choose a better code and better gadgets, to drive the error rate down to a point where the implementation is likely to work. Theoretically speaking, a simple way to argue that this is possible is to concatenate. That is to say, we can think of the fault-tolerant implementation of the original circuit as if it were any other quantum circuit, and then implement this new circuit fault-tolerantly, using the same scheme. We can then do this again and again, as many times as we need to drive the error rate down to a level that allows the original computation to work.

To get a rough idea for how the error rate decreases through this method, let's consider how it works for a few iterations. We start with the error probability $p$ for locations the original circuit, and presuming that $p< p_{\text{th}} = 1/C,$ this rate goes down to $Cp^2 = (Cp) p$ after the first iteration. By treating the fault-tolerant implementation as any other circuit, and implementing it fault-tolerantly, we obtain a logical error rate of

C \bigl((Cp) p \bigr)^2 = (Cp)^3 p.

Another iteration reduces the error further, to

C \bigl((Cp)^3 p \bigr)^2 = (Cp)^7 p.

Continuing in this manner for a total of $k$ iterations leads to a logical error rate (for the original circuit) of

(Cp)^{2^k - 1} p,

which is doubly exponential in $Cp.$

This means that we don't need too many iterations to make the error rate extremely small. Meanwhile the circuits are growing in size with each level of concatenation — but the size only increases singly-exponentially in the number of levels $k$ because, with each level of fault-tolerance, the size grows by at most a factor determined by the maximum size of the gadgets being used. When it is all put together, and an appropriate choice for the number of levels of concatenation is made, we obtain the threshold theorem.

So, what is this threshold value in reality? The answer is that it depends on the code and the gadgets used. For the Steane code together with magic state distillation, it is minuscule and probably unlikely to be achievable in practice. But, using surface codes and state of the art gadgets, the threshold has been estimated to be around 1%.

As new codes and methods are discovered, it is reasonable to expect the threshold value to increase, while simultaneously the level of noise in actual physical components will decrease. Reaching the point at which large-scale quantum computations can be implemented fault-tolerantly will not be easy, and will not happen overnight. But, this theorem together with advances in quantum codes and quantum hardware provide optimism — and we continue to push forward to reach this ultimate goal of building a large-scale fault-tolerant quantum computer.

Was this page helpful?

Yes