# 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 or better – that is, less than one error in every gates that we execute. However, the hardware we have talked about this week has error rates that range from to perhaps , 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 , since it
takes three bits to transmit a one-bit message. More generally, if
the code uses bits to encode of message, then the rate is
.

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, , 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 , 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 , then the probability of this happening is .
For example, if , then . 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. , 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 bits, the
probability of errors occurring is
. ( is the *binomial
coefficient* from basic probability and statistics, also sometimes
written .) If we are holding , the probability that
we started with 000 and two errors occurred (what actually happened)
is , but the probability that we started with 111 and only
error occurred is . 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, .

© Keio University