Quantum Error-Correcting Codes

Quantum states are very delicate. The primary difference between a quantum state and a classical state is that a quantum state can be in a superposition of multiple different classical states. However, any measurement of the superposition will collapse the quantum state into one of its component classical states. In fact, most interactions with the environment will act just like a measurement and will collapse the state. This is the reason the world at a human scale looks classical - big objects are very likely to interact at least a little bit with their environment, so they are constantly collapsing into classical states. This process is known as decoherence.

This is a big problem for a quantum computer. If we cannot stop it from interacting with the environment, it will be no better than a classical computer. It turns out that stopping decoherence is the same problem as stopping general noise, such as a coherent bit flip. The solution to the problem is to use a quantum error-correcting code.

The simplest classical error-correcting code is the repetition code. We encode a 0 as 000 and a 1 as 111. Then if only one bit is flipped, we might get the state 011, and we can deduce that the original state was 111.

For a quantum code, we need a bit more. The signs of states in a quantum superposition are important, so we need to be able to correct sign errors as well as bit flip errors. To do this, we could use nine qubits instead of three:

|0> -> (|000> + |111>) (|000> + |111>) (|000> + |111>)
|1> -> (|000> - |111>) (|000> - |111>) (|000> - |111>).

Then by comparing qubits within blocks of three, we can detect bit flip errors, and by comparing the signs of the three blocks, we can detect sign errors. Using this code, we can correct an arbitrary single-qubit quantum error.

This is just the simplest quantum code. Many more are known, and there is a well-developed theory of quantum error-correcting codes. Most quantum codes can be described by their code stabilizers, which is much simpler than writing out the full state in ket notation.

If we want to preserve a quantum state for a long time without doing any calculations, or if we want to send it through a noisy communications channel, we can just encode the state using a quantum code and decode it when we are done. If we want to do computation on a state using noisy gates, we need to know how to perform operations on states that are already encoded. Furthermore, we need to do it in such a way that we do not introduce more errors than we can correct. In other words, we need the computation to be fault-tolerant.

Back to Daniel Gottesman's home page - Quantum error correction sonnet

February 25, 1999