3.14

# Classical Error Correction

In the first week of the course, we discussed the decoherence of quantum states caused by noise and imperfections in our control systems.

Decoherence results in errors in our states or gates. We saw when we discussed Shor’s algorithm that our systems need to be nearly perfect in order to be useful, with error rates of $10^{-13}$ or better – that is, less than one error in every $10^{13}$ gates that we execute. However, the hardware we have talked about this week has error rates that range from $10^{-3}$ to perhaps $10^{-5}$, depending on experimental conditions and the particular technology. So is computation simply beyond our technical capabilities for the foreseeable future?

Our hope lies in quantum error correction. First, let’s review the basic idea of error correction, then look at the behavior of quantum errors in this article, before studying the mechanisms used in the next article.

## Error Correction Concepts

Classical computers depend heavily on error correcting codes, the core ideas of which were developed originally by Richard W. Hamming back in 1947. Today, there are many different known choices of error correcting code. Fundamentally, error correcting codes add redundancy to the information in a message, then use that redundancy to detect and correct errors that occur in transmission or storage of data.

The simplest approach is simply to repeat information: if you want to send a 0, send 00 instead; if you want to send a 1, send 11. With two copies of the data, it is easy to detect an error. If the receiver receives 01 or 10, she knows that an error has occurred. Unfortunately, she doesn’t know which the correct state is, since the result is now ambiguous. The minimum number of copies necessary to be able to recover the original state is three: a single error then results in a state such as 001 or 010, from which it is easy to infer that the most likely original message was intended to be 000 (or just 0, once decoded). Such an error is called a bit flip.

In this simple repetition code, we refer to 000 and 111 as our code words. The code words associated with a particular choice of error correcting code are the legitimate states. Collectively, they make up the code space. The code rate in this case is $1/3$, since it takes three bits to transmit a one-bit message. More generally, if the code uses $n$ bits to encode $k$ of message, then the rate is $k/n$.

The number of bits that must be flipped to move from one code word to another is the code distance. With our triple repetition code, all three bits must be flipped, $000\rightarrow 001\rightarrow 011\rightarrow 111$, so the code distance is three.

## Code Words, Distance and Error Probability

The code distance for a particular error correcting code (whether quantum or classical) is known as the Hamming distance. It’s the number of bit flips required to move from one code word to another. If the code distance is $d = 3$, then three bits must be flipped to move from 000 to 111 or vice versa. If this happens, the errors go completely undetected; it is impossible to recognize that anything untoward has happened. If the probability of any individual bit being in error is $p$, then the probability of this happening is $p^d = p^3$. For example, if $p = 10^{-3}$, then $p^3 = 10^{-9}$. Our error rate has suddenly dropped from one in a thousand to one in a billion.

However, it’s not quite that simple. If two errors occur, e.g. $000\rightarrow 001\rightarrow 101$, then we have a state that’s not one of the code words, and recognize that at least one error has occurred. We say that we are outside of the code space, and must decide how to correct the state. With $n$ bits, the probability of $e$ errors occurring is $\binom{n}{e}p^e(1-p)^{n-e}$. ($\binom{n}{e}$ is the binomial coefficient from basic probability and statistics, also sometimes written $_n C_k$.) If we are holding $101$, the probability that we started with 000 and two errors occurred (what actually happened) is $p^2(1-p)$, but the probability that we started with 111 and only error occurred is $p(1-p)^2$. The latter appears to be more likely, so we will choose “correct” back to 111, perpetuating an error and ruining our data. The fundamental rule is that an error correcting code can only correct errors less than half of the code distance, $% $.