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.

Lesson video

In the following video, John Watrous steps you through the content in this lesson on fault-tolerant quantum computing. Alternatively, you can open the YouTube video for this lesson in a separate window. Download the slides for this lesson.