General ideas
Data can be affected by “noise”, that is, any unwanted interactions with the rest of the environment which result in a modification of the data. This leads to errors in computations. As the name indicates, the idea of “error correction” is to try to correct these errors. To achieve this, the solution is to introduce redundancy by spreading the information one needs to protect in a bigger system. This way, even if part of the data is corrupted by noise, one can still recover the initial information. The bigger system is thus referred to as an error-correcting code: it encodes the information in such a way that errors can be detected and then corrected. There exist both classical error-correcting codes (to correct errors affecting classical data) and quantum error-correcting codes (to correct errors affecting quantum data).
A quantum bit encoded into a quantum error-correcting code is called a quantum error-corrected qubit.
To better understand the concept of error correction, it is useful to consider an example.
The classical repetition code
In classical computers, the information is spelled out in bits which can take the value \( 0 \) or \( 1 \). The only error that can occur is a bit-flip: a \( 0 \) turning into a \( 1 \) or a \( 1 \) turning into a \( 0 \). The conceptually-easiest way to protect the information from such an error is to repeat the information: one may for instance repeat each bit three times. A logical bit \( 0 \) will then be represented by a string of three zeros while a logical bit 1 will be represented by three ones, \( 0L=000,1L=111 \). Because of noise, one may end up with a string made of three non-identical bits, such as \( 001 \). However, if the probability of having an erroneous bit is smaller than that of having no error, the most probable option is that the original string of bits was \( 000 \) and that the last bit flipped. Most of the time, performing a majority vote will then recover the initial state.
Although it is not completely straightforward, the classical repetition code can also be generalized to the quantum setting. There also exist more efficient codes, both in the classical and quantum cases.
Desired characteristics for an error-correcting code
- One wants to be able to protect the information against as much noise as possible. This is captured by a notion known as the distance of the code.
- One wants to correct the errors using as few resources as possible.
- It should be easy to detect what the errors are and to correct them.
Frequently-asked questions on error correction
- Why is quantum error correction needed? Quantum information is much more sensitive to its environment than classical information. While mitigating the effect of noise on data may be sufficient to achieve certain near-term applications of quantum computing which require to perform only relatively few operations on relatively few quantum bits (qubits), it is expected that this will not be enough for longer-term applications. Assuming each operation performed succeeds with probability 99.9% independently of the success of other gates, an error will occur after every thousand operations on average. For comparison, it has recently been estimated that factoring an integer made of 617 digits (the kind of numbers used for encryption) would require \( 10^12 \) gates using Shor’s famous quantum algorithm.
- Why is quantum error correction harder than classical error correction? Quantum error correction comes with certain difficulties that are inherent to the quantum world. For instance, generalizing the classical repetition code cannot simply be done by copying qubits several times as this is forbidden by the no-cloning theorem. The latter indeed asserts that there does not exist a general procedure to copy any arbitrary quantum state. Moreover, a general principle in quantum mechanics is that one cannot learn information on an unknown quantum state without modifying this state. In particular, it will not be possible to simply read out the state of a qubit like one would read out the value of a bit. Finally, while only one type of error (the bit flip) can affect classical bits, a whole continuum of errors may affect qubits. Thankfully, despite all these complications, quantum error correction is nonetheless possible. See the glossary entry “error-corrected qubit” to learn about stabilizer codes, an important class of error-corrected qubits.
The content of this glossary entry is mostly taken from the first lessons of the module “Introduction to quantum error correction” of our Training Centre. To learn more on this topic, check out the full learning path “On the way to fault tolerance”.
