Why error-correction and a model for it#

Why do we need error-correction?#

All computational and communication tasks are done with physical apparatus, and such apparatus is often noisy and unreliable. This means that there is a non-zero chance that the apparatus makes errors in the execution of its processes. One solution to this problem is to try and manufacture better devices. But this is not always possible, either because there is no known way of making better devices or because it is far too costly to make near perfect devices.

Thankfully, we have discovered procedures and algorithms that can be used to increase the probability that our noisy hardware outputs the correct results, with a modest increase in costs. The field of study that deals with such procedures and algorithms is called error-correction.

This field first emerged in tandem with the development of analog and digital classical communication and computation devices in the middle of the twentieth century. Today, classical error-correction is a mature field, whose results are applied in a wide variety of circumstances. For example, if the computer you are using to read this book is connected to the internet via Wi-Fi, then there is error-correcting algorithms being employed by your computer and the router to detect if any of the received packets were corrupted during transmission.

On the other hand, the field of quantum error-correction, which concerns error-correction techniques on quantum communication and computing devices, began in the late 1990s. Since then it has made rapid advancements, and many techniques and concrete algorithms have been discovered. This is very encouraging, because the hardware for quantum computers is so small and sensitive, it seems unlikely that we will ever be able to make physical error rates small enough to build quantum computers without the need for error-correction.

A model for error-correction problems#

To understand the field, it is best to start with a simple problem that captures the essence of the field. This simple problem for error-correction, both classical and quantum, has an abstract model which we now present.

Alice wants to send information to Bob via a transmission line or channel connecting them. The information could be a string of bits in the classical case, or a string of qubits in the quantum case. Pictorially, we have the following scenario.

As you can see, we assume that the channel is noisy, so any information is subject to errors during transmission. On the other hand, we will assume, Alice and Bob have perfect apparatus, which allows them to execute error-correction algorithms with no errors.

This is our basic model for error-correction problems. It seems like it is a specialized to a communication problem, but with a little bit of imagination, we can see how it applies to other types of problems as well. For example, a computer memory can deteriorate over time, causing the stored information to be corrupted. In this scenario, Alice is the person who initially recorded the information to the memory. The noisy channel in this case is across time, rather than space as above, because the memory stays in place and over time gets corrupted. Bob is the person who attempts to read the memory at a later point in time.

Our goal#

Our goal, over the next few chapters, is to design procedures for Alice and Bob to communicate reliably, under the above model. We will do so for both the classical and the quantum case.

However, as we will discuss in detail later, this model does not capture all interesting problems that are studied by the field of error-correction. The most important such problem is that of performing quantum computation with unreliable hardware. In this case, there is no part of our system that is error-free and therefore, the problem becomes much more difficult to solve. Fortunately, we will discover that there are algorithms, called fault-tolerant algorithms, that will work for such problems as well. Fault-tolerance algorithms will be the subject of latter chapters of this book.

No quantum without classical#

To have a good understanding of quantum error-correction, it is essential to first start by learning the fundamentals of classical error-correction. There are a few reasons for it. The first is that classical algorithms are often conceptually simpler than quantum, and therefore easier to understand. Secondly, many quantum error-correction algorithms are directly or indirectly constructed from classical error-correction algorithms. Therefore, if one is to learn how to do this, one should be aware of the properties of the classical algorithms.

Therefore, in this book, we will first spend some time learning about classical error-correction. As we will refer to this material often later on, the reader should not skip it.