Rather than have a general discussion of codes and error-correction, we
will instead look at some of the simplest examples. One of the most
straightforward error-correcting codes is the *repetition code*. To
encode a 1 bit message in the repetition code, we simply copy it several
times (say 3 times): \(0\) encodes to \(000\) and \(1\) encodes to
\(111\). Suppose now that we store the *codeword* \(000\) or \(111\) in
a memory for a period of time and, during that time, errors occur. A
simple model of errors is to suppose that each bit can flip randomly
with some probability \(p<1/2\) and that the error process acts
independently on each bit. If one error occurs, the stored codeword
becomes one of \(\{001,010,100\}\) or one of \(\{110,101,011\}\),
respectively. Given an encoded message \(abc\), the original message is
the value indicated by a majority of the bits
\(\mathrm{MAJ}(a,b,c)=ab\oplus bc\oplus ca\). For example, if we read
\(001\) from the memory, the majority value is obviously \(0\), but we
could also have computed it from the formula for
\(\mathrm{MAJ}(0,0,1)\). This recovery procedure works if only one
error occurs; it fails otherwise. However, correcting even a single
error is enough to reduce the probability of failure, since the
probability of more than one error is \(3p^2(1-p)+p^3=3p^2-2p^3\), which
is less than \(p\) whenever \(p<1/2\). The reduction in error rate can
be surprisingly large: if \(p\) is 1 percent, the failure probability
after encoding is less than 0.03 percent.

The repetition code is a classical error-correcting code, but there is a closely related quantum repetition code that is one of the simplest quantum codes. Again, rather than defining quantum codes in general, we will describe a 3-qubit quantum bit-flip code and look at how to encode, decode, and detect errors.

To encode a single-qubit message \(|\psi\rangle=\alpha
|0\rangle+\beta |1\rangle\) in the 3-qubit quantum bit-flip code,
we apply a quantum circuit that encodes the messages \(0\) and \(1\)
in superposition so that \(|\psi\rangle\) encodes to \(\alpha
|000\rangle + \beta |111\rangle\). A very important quantum
result is that, for arbitrary \(\alpha\), we cannot create identical
copies of \(|\psi\rangle\), like (\(\alpha |0\rangle + \beta
|1\rangle\))(\(\alpha |0\rangle + \beta |1\rangle\))(\(\alpha
|0\rangle + \beta |1\rangle\)), which is the way the classical
repetition code would operate. Instead, we can make repetitions with
the codewords. Now, when the message is an equal superposition
\(\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)\), the encoded message
happens to be an entangled state, since it cannot be written as a
tensor product of two or more states. The “*Encoder into bit-flip
code*” example encodes qubit 2 into the quantum bit-flip code. The
first three gates in the example prepare qubit 2 in the state
\(\cos(\pi/8)|0\rangle-i\sin(\pi/8)|1\rangle\) and the
remaining gates encode this state into the code.

Suppose that we store the quantum codeword for a period of time and
the qubits begin to decohere. It is not obvious, but the error
operators that arise from independent decoherence processes on each
qubit can be written as linear combinations of the identity operator
and the Pauli operators \(X\), \(Y=-iZX\), and \(Z\). Since quantum
mechanics is a linear theory, it suffices to correct only the bit-flip
\(X\) and phase-flip \(Z\) errors [Shor
(1995)].
This is a remarkable observation. By correcting only a discrete set of
errors, weighted sums of those errors – and hence a continuum of
errors – can be corrected as well.

That said, the quantum bit-flip code is unable to correct any
phase-flip errors that occur (hence its name). A phase flip on any
qubit changes the encoded message to \(\alpha |000\rangle - \beta
|111\rangle\), but this state is an encoding of the 1 qubit message
\(\alpha |0\rangle - \beta |1\rangle\), which is a valid
codeword too. Hence, the quantum bit-flip code is not “strong enough”
to correct realistic errors since it is unable to correct phase
errors. While we do not discuss them here, there are quantum codes
that can detect and correct the most general types of errors, such as
Shor’s code [Shor
(1995)].

The quantum bit-flip code does correct bit-flip errors. We will
briefly describe two procedures for detecting and correcting a
bit-flip error using the 3-qubit code.

The second example below, “*Bit-flip encoder and decoder*,” implements
a reversible majority voter to decode the bit-flip code. The identity
gates in the circuit represent noise, and you can replace them with
various operations, such as bit flips \(X\), to test the decoder.
Following the identity gates, a pair of CNOT gates (with Hadamard
gates) computes \(abc\mapsto a\oplus b, b, c\oplus b\). The
remaining T, CNOT, and H gates that target qubit 2 compute
\(\mathrm{MAJ}(a,b,c)\) into qubit 2, which we characterize using
state tomography. Qubits 1 and 3 carry information about what errors
occurred and remain unobserved. Even without explicitly inserting any
errors, an experiment or realistic simulation will decode to a
different point on the Bloch sphere because (a) the codeword is
unprotected against phase errors and (b) the encoder and decoder are
not ideal operations.

The third example below, “*Encoder into bit-flip code with parity
checks*,” implements parity measurements to detect errors. The first
set of gates prepares the input state to the encoder, in this case
\(\cos(\pi/8)|0\rangle-i\sin(\pi/8)|1\rangle\). The second set
of gates is the encoder followed by a SWAP, so that qubits 0, 1, and 3
contain the codeword. The third and final set of gates implements two
parity computations: the parity of qubits 0 and 1 is computed into
qubit 4, and the parity of qubits 1 and 3 is computed into qubit 2.
Let’s call the outcome of measuring qubit 4 by the name \(s_0\) and
the outcome of measuring qubit 2 by the name \(s_1\). The pair of
bits \(s=s_0s_1\) is called the *error syndrome*. If no error or
just a single bit-flip error occurs, the error syndrome \(s\) reveals
the location of the bit-flip error. Specifically, if \(s=00\) then no
error occurred, if \(s=01\) then qubit 3 is flipped, if \(s=10\) then
qubit 0 is flipped, and if \(s=11\) then qubit 1 is flipped.
Importantly, the act of measuring the error syndrome discretizes the
error! After measuring quantum codeword in the standard basis, we
obtain three outcome bits \(abc\) that are correlated with an error
syndrome \(s\) and can use \(s\) to correct the outcome bits. For
example, if we measure the outcome \(001\) (qubits 0, 1, 3) with error
syndrome \(01\) (qubits 2 and 4) then we correct \(001\) to \(000\).
Each three bit outcome \(abc\) is corrected to one of \(000\) or
\(111\), and we expect to observe these with probability near
\(\cos^2(\pi/8)\) and \(\sin^2(\pi/8)\), respectively, if the
bit-flip error rate it not too high.