Repetition codes

We'll begin the lesson with a discussion of repetition codes. Repetition codes don't protect quantum information against every type of error that can occur on qubits, but they do form the basis for the 9-qubit Shor code, which we'll see in the next lesson, and they're also useful for explaining the basics of error correction.

---

Classical encoding and decoding

Repetition codes are extremely basic examples of error correcting codes. The idea is that we can protect bits against errors by simply repeating each bit some fixed number of times.

In particular, let's first consider the 3-bit repetition code, just in the context of classical information to start. This code encodes one bit into three by repeating the bit three times, so $0$ is encoded as $000$ and $1$ is encoded as $111.$

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

If nothing goes wrong, we can obviously distinguish the two possibilities for the original bit from their encodings. The point is that if there was an error and one of the three bits flipped, meaning that a 0 changes into a 1 or a 1 changes to a 0, then we can still figure out what the original bit was by determining which of the two binary values appears twice. Equivalently, we can decode by computing the majority value (i.e., the binary value that appears most frequently).

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

Of course, if 2 or 3 bits of the encoding flip, then the decoding won't work properly and the wrong bit will be recovered, but if at most 1 of the 3 bits flip, the decoding will be correct. This is a typical property of error correcting codes in general: they may allow for the correction of errors, but only if there aren't too many of them.

Noise reduction for the binary symmetric channel

For an example of a situation in which the chances of making an error can be decreased using a repetition code, suppose that our goal is to communicate a single bit to a hypothetical receiver, and we're able to transmit bits through a so-called binary symmetric channel, which flips each bit sent through it independently with some probability $p.$ That is, with probability $1-p,$ the receiver gets whatever bit was sent through the channel, but with probability $p,$ the bit-flips and the receiver gets the opposite bit value.

So, if we choose not to use the 3-bit repetition code, and simply send whatever bit we have in mind through the channel, the receiver therefore receives the wrong bit with probability $p.$ On the other hand, if we first encode the bit we want to send using the 3-bit repetition code, and then send each of the three bits of the encoding through the channel, then each one of them flips independently with probability $p.$ The chances of a bit-flip are now greater because there are now three bits that might flip rather than one, but if at most one of the bits flips, then the receiver will decode correctly. An error therefore persists after decoding only if two or more of the bits flip during transmission.

The probability that two bits flip during transmission is $3p^2(1-p),$ which is $p^2(1-p)$ for each of the three choices for the bit that doesn't flip, while the probability that all three bits flip is $p^3.$ The total probability of two or three bit-flips is therefore

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

For values of $p$ smaller than one-half, this results in a decrease in the probability that the receiver ends up with the wrong bit. There will still be a chance of an error in this case, but the code decreases the likelihood. (For values of $p$ greater than one-half, on the other hand, the code actually increases the likelihood that the receiver gets the wrong bit.)

---

Encoding qubits

The 3-bit repetition code is a classical error correcting code, but we can consider what happens if we try to use it to protect qubits against errors. As we'll see, it's not a very impressive quantum error correcting code, because it actually makes some errors more likely. It is, however, the first step toward the Shor code, and will serve us well from a pedagogical viewpoint.

To be clear, when we refer to the 3-bit repetition code being used for qubits, we have in mind an encoding of a qubit where standard basis states are repeated three times, so that a single-qubit state vector is encoded as follows.

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

This encoding is easily implemented by the following quantum circuit, which makes use of two initialized workspace qubits and two controlled-NOT gates.

Notice, in particular, that this encoding is not the same as repeating the quantum state three times, as in a given qubit state vector being encoded as $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Such an encoding cannot be implemented for an unknown quantum state $\vert\psi\rangle$ by the no cloning theorem.

Bit-flip errors

Now suppose that an error takes place after the encoding has been performed. Specifically, let's suppose that an $X$ gate, or in other words a bit-flip, occurs on one of the qubits. For instance, if the middle qubit experiences a bit-flip, the state of the three qubits is transformed into this state:

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

Of course, this isn't the only sort of error that could occur — and it's also reasonable to question the assumption that an error takes the form of a perfect, unitary operation. We'll return to these issues in the last section of the lesson, and for now we can view an error of this form as being just one possible type of error (albeit a fundamentally important one).

We can see clearly from the mathematical expression for the state above that the middle bit is the one that's different inside of each ket. But suppose that we had the three qubits in our possession and didn't know their state. If we suspected that a bit-flip may have occurred, one option to verify that a bit flipped would be to perform a standard basis measurement, which, in the case at hand, would cause us to see $010$ or $101$ with probabilities $\vert\alpha\vert^2$ and $\vert\beta\vert^2,$ respectively. In either case, our conclusion would be that the middle bit flipped — but, unfortunately, we would lose the original quantum state $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ This is the state we're trying to protect, so measuring in the standard basis is an unsatisfactory option.

What we can do instead is to use the following quantum circuit, feeding the encoded state into the top three qubits. This circuit nondestructively measures the parity of the standard basis states of the top two qubits as well as the bottom two qubits of the three-qubit encoding.

Under the assumption that at most one bit flipped, one can easily deduce from the measurement outcomes the location of the bit-flip (or the absence of one). In particular, as the following four circuit diagrams illustrate, the measurement outcome $00$ indicates that no bit-flip occurred, while the three other possibilities indicate which qubit experienced a bit-flip.

Crucially, the state of the top three qubits does not collapse in any of the cases, which allows us to correct a bit-flip error if one has occurred — by simply applying the same bit-flip again with an $X$ gate. The following table summarizes the states we obtain from at most one bit-flip, the measurement outcomes (which are called the syndrome in the context of error correction), and the correction needed to get back to the original encoding.

Once again, we're only considering the possibility that at most one bit-flip occurred. This wouldn't work correctly if two or three bit-flips occurred, and we also haven't considered other possible errors besides bit-flips.

Phase-flip errors

In the quantum setting, bit-flip errors aren't the only errors we need to worry about. For instance, we also have to worry about phase-flip errors, which are described by $Z$ gates. Along the same lines as bit-flip errors, we can think about phase-flip errors as representing just another possibility for an error that can affect a qubit.

However, as we will see in the last section of the lesson, which is on the so-called discretization of errors for quantum error correcting codes, a focus on bit-flip errors and phase-flip errors turns out to be well-justified. Specifically, the ability to correct a bit-flip error, a phase-flip error, or both of these errors simultaneously automatically implies the ability to correct an arbitrary quantum error on a single qubit.

Unfortunately, the 3-bit repetition code doesn't protect against phase-flips at all. For instance, suppose that a qubit state $\alpha\vert 0\rangle + \beta\vert 1\rangle$ has been encoded using the 3-bit repetition code, and a phase-flip error occurs on the middle qubit. This results in the state

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

which is exactly the state we would have obtained from encoding the qubit state $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ Indeed, a phase-flip error on any one of the three qubits of the encoding has this same effect, which is equivalent to a phase-flip error occurring on the original qubit prior to encoding. Under the assumption that the original quantum state is an unknown state, there's therefore no way to detect that an error has occurred, because the resulting state is a perfectly valid encoding of a different qubit state. In particular, running the error detection circuit from before on the state $\alpha \vert 000\rangle - \beta \vert 111\rangle$ is certain to result in the syndrome $00,$ which wrongly suggests that no errors have occurred.

Meanwhile, there are now three qubits rather than one that could potentially experience phase-flip errors. So, in a situation in which phase-flip errors are assumed to occur independently on each qubit with some nonzero probability $p$ (similar to a binary symmetric channel except for phase-flips rather than bit-flips), this code actually increases the likelihood of a phase-flip error after decoding for small values of $p.$ To be more precise, we'll get a phase-flip error on the original qubit after decoding whenever there are an odd number of phase-flip errors on the three qubits of the encoding, which happens with probability

$$3 p (1 - p)^2 + p^3.$$

This value is larger than $p$ when $0<p<1/2,$ so the code increases the probability of a phase-flip error for values of $p$ in this range.

Modified repetition code for phase-flip errors

We've observed that the 3-bit repetition code is completely oblivious to phase-flip errors, so it doesn't seem to be very helpful for dealing with this sort of error. We can, however, modify the 3-bit repetition code in a simple way so that it does detect phase-flip errors. This modification will render the code oblivious to bit-flip errors — but, as we'll see in the next section, we can combine together the 3-bit repetition code with this modified version to obtain the Shor code, which can correct both bit-flip and phase-flip errors.

Here is the modified version of the encoding circuit from above, which will now be able to detect phase-flip errors. The modification is very simple: we simply apply a Hadamard gate to each qubit after performing the two controlled-NOT gates.

A Hadamard gate transforms a $\vert 0\rangle$ state into a $\vert + \rangle$ state, and a $\vert 1\rangle$ state into a $\vert - \rangle$ state, so the net effect is that the single qubit state $\alpha\vert 0\rangle + \beta \vert 1\rangle$ is encoded as

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

where $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ and $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

A phase-flip error, or equivalently a $Z$ gate, flips between the states $\vert + \rangle$ and $\vert - \rangle,$ so this encoding will be useful for detecting (and correcting) phase-flip errors. Specifically, the error-detection circuit from earlier can be modified as follows.

In words, we take the circuit from before and simply put Hadamard gates on the top three qubits at both the beginning and the end. The idea is that the first three Hadamard gates transform $\vert + \rangle$ and $\vert - \rangle$ states back into $\vert 0\rangle$ and $\vert 1\rangle$ states, the same parity checks as before take place, and then the second layer of Hadamard gates transforms the state back to $\vert + \rangle$ and $\vert - \rangle$ states so that we recover our encoding. For future reference, let's observe that this phase-flip detection circuit can be simplified as follows.

The following four circuit diagrams describe how our modified version of the 3-bit repetition code, including the encoding step and the error detection step, functions when at most one phase-flip error occurs. The behavior is similar to the ordinary 3-bit repetition code for bit-flips.

Here's an analogous table to the one from above, this time considering the possibility of at most one phase-flip error.

Unfortunately, this modified version of the 3-bit repetition code can now no longer correct bit-flip errors. All is not lost, however. As suggested previously, we'll be able to combine the two codes we've just seen into one code — the 9-qubit Shor code — that can correct both bit-flip and phase-flip errors, and indeed any error on a single qubit.