The 9-qubit Shor code

Now we turn to the 9-qubit Shor code, which is a quantum error correcting code obtained by combining together the two codes considered in the previous section: the 3-bit repetition code for qubits, which allows for the correction of a single bit-flip error, and the modified version of that code, which allows for the correction of a single phase-flip error.

---

Code description

The 9-qubit Shor code is the code we obtain by concatenating the two codes from the previous section. This means that we first apply one encoding, which encodes one qubit into three, and then we apply the other encoding to each of the three qubits used for the first encoding, resulting in nine qubits in total.

To be more precise, while we could apply the two codes in either order in this particular case, we'll make the choice to first apply the modified version of the 3-bit repetition code (which detects phase-flip errors), and then we'll encode each of the resulting three qubits independently using the original 3-bit repetition code (which detects bit-flip errors). Here is a circuit diagram representation of this encoding.

As the figure suggests, we'll think about the nine qubits of the Shor code as being grouped into three blocks of three qubits, where each block is obtained from the second encoding step (which is the ordinary 3-bit repetition code). The ordinary 3-bit repetition code, which here is applied three times independently, is called the inner code in this context, whereas the outer code is the code used for the first encoding step, which is the modified version of the 3-bit repetition code that detects phase-flip errors.

We can alternatively specify the code by describing how the two standard basis states for our original qubit get encoded.

$$\begin{aligned} \vert 0\rangle & \:\mapsto\: \frac{1}{2\sqrt{2}} (\vert 000\rangle + \vert 111\rangle) \otimes (\vert 000\rangle + \vert 111\rangle) \otimes (\vert 000\rangle + \vert 111\rangle) \\[4mm] \vert 1\rangle & \:\mapsto\: \frac{1}{2\sqrt{2}} (\vert 000\rangle - \vert 111\rangle) \otimes (\vert 000\rangle - \vert 111\rangle) \otimes (\vert 000\rangle - \vert 111\rangle) \end{aligned}$$

Once we know this, we can determine by linearity how an arbitrary qubit state vector is encoded.

---

Correcting bit-flip and phase-flip errors

Errors and CNOT gates

To analyze how $X$ and $Z$ errors affect encodings of qubits, both for the 9-qubit Shor code as well as other codes, it will be helpful to observe a few simple relationships between these errors and CNOT gates. As we begin to analyze the 9-qubit Shor code, this is a reasonable moment to pause to do this.

The following circuit diagrams illustrate three basic relationships among $X$ gates and CNOT gates. Specifically, applying an $X$ gate to the target qubit prior to a CNOT is equivalent to swapping the order and performing the CNOT first, but applying an $X$ gate to the control qubit prior to a CNOT is equivalent to applying $X$ gates to both qubits after the CNOT. Finally, applying $X$ gates to both qubits prior to a CNOT is equivalent to applying the CNOT first and then applying an $X$ gate to the control qubit. These relationships can be verified by performing the required matrix multiplications or computing the effect of the circuits on standard basis states.

The situation is similar for $Z$ gates, except that the roles of the control and target qubits switch. In particular, we have the three relationships depicted by the following quantum circuits.

Correcting bit-flip errors

Now we'll consider how errors can be detected and corrected using the 9-qubit Shor code, starting with bit-flip errors — which we'll generally refer to as $X$ errors hereafter for the sake of brevity.

To detect and correct $X$ errors, we can simply treat each of the three blocks in the encoding separately. Each block is an encoding of a qubit using the 3-bit repetition code, which protects against $X$ errors — so by performing the syndrome measurements and $X$ error corrections described previously to each block, we can detect and correct up to one $X$ error per block. In particular, if there is at most one $X$ error on the nine qubits of the encoding, this error will be detected and corrected by this procedure.

In short, correcting bit-flip errors is a simple matter for this code, due to the fact that the inner code corrects bit-flip errors.

Correcting phase-flip errors

Next we'll consider phase-flip errors, or $Z$ errors for brevity. This time it's not quite as clear what we should do because the outer code is the one that detects $Z$ errors, but the inner code seems to be somehow "in the way," making the detection and correction of these errors slightly more difficult.

Suppose that a $Z$ error occurs on one of the 9 qubits of the Shor code, such as the one indicated in this diagram.

We've already observed what happens when a $Z$ error occurs when we're using the 3-bit repetition code — it's equivalent to a $Z$ error occurring prior to encoding. In the context of the 9-qubit Shor code, this means that a $Z$ error on any one of the three qubits within a block always has the same effect, which is equivalent to a $Z$ error occurring on the corresponding qubit prior to the inner code being applied.

For example, the circuit diagram above is equivalent to the following diagram. This can be reasoned using the relationships between $Z$ and CNOT gates described above, or by simply evaluating the circuits on an arbitrary qubit state $\vert\psi\rangle.$

This suggests one option for detecting and correcting $Z$ errors, which is to decode the inner code, leaving us with the three qubits used for the outer encoding along with six initialized workspace qubits. We can then check these three qubits of the outer code for $Z$ errors, and then finally we can re-encode using the inner code, to bring us back to the 9-qubit encoding we get from the Shor code. If we do detect a $Z$ error, we can either correct it prior to re-encoding with the inner code, or we can correct it after re-encoding, by applying a $Z$ gate to any of the qubits in that block.

Here's a circuit diagram that includes the encoding circuit and the error suggested above together with the steps just described (but not the actual correction step).

In this particular example, the syndrome measurement is $11,$ which locates the $Z$ error as having occurred on one of the qubits in the middle block.

One advantage of correcting $Z$ errors after the re-encoding step rather than before is that we can simplify the circuit above. The following circuit is equivalent, but requires four fewer CNOT gates.

Once again, the syndrome doesn't indicate which qubit has been affected by a $Z$ error, but rather which block has experienced a $Z$ error, with the effect being the same regardless of which qubit within the block was affected. We can then correct the error by applying a $Z$ gate to any of the three qubits of whichever block was affected.

As an aside, here we see an example of degeneracy in a quantum error-correcting code, where we're able to correct certain errors ($Z$ errors in this case) without being able to identify them uniquely.

Simultaneous bit- and phase-flip errors

We've now seen how both $X$ and $Z$ errors can be detected and corrected using the 9-qubit Shor code, and in particular how at most one $X$ error or at most one $Z$ error can be detected and corrected. Now let's suppose that both a bit-flip and a phase-flip error occur, possibly on the same qubit. As it turns out, nothing different needs to be done in this situation from what has already been discussed — the code is able to detect and correct up to one $X$ error and one $Z$ error simultaneously, without further modification.

To be more specific, $X$ errors are detected by applying the ordinary 3-bit repetition code syndrome measurement, which is performed separately on each of the three blocks of three qubits; and $Z$ errors are detected through the procedure described just above, which is equivalent to decoding the inner code, performing the syndrome measurement for the modified 3-bit repetition code for phase-flips, and then re-encoding. These two error detection steps — as well as the corresponding corrections — can be performed completely independently of one another, and in fact it doesn't matter in which order they're performed.

To see why this is, consider the example depicted in the following circuit diagram, where both an $X$ and a $Z$ error have affected the bottom qubit of the middle block.

Let's first observe that the ordering of the errors doesn't matter, in the sense that reversing the position of the $X$ and $Z$ errors yields an equivalent circuit. To be clear, $X$ and $Z$ do not commute, they anti-commute:

$$XZ = \begin{pmatrix} 0 & 1\\[1mm] 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0\\[1mm] 0 & -1 \end{pmatrix} = \begin{pmatrix} 0 & -1\\[1mm] 1 & 0 \end{pmatrix} = - \begin{pmatrix} 1 & 0\\[1mm] 0 & -1 \end{pmatrix} \begin{pmatrix} 0 & 1\\[1mm] 1 & 0 \end{pmatrix} = -ZX.$$

This implies that the following circuit is equivalent to the one just above up to a global phase factor of $-1.$

We can now move the $Z$ error just like before to obtain another equivalent circuit.

At this point it's evident that if the procedure to detect and correct $X$ errors is performed first, the $X$ error will be corrected, after which the procedure for detecting and correcting $Z$ errors can be performed to eliminate the $Z$ error as before.

Alternatively, the procedure to detect and correct $Z$ errors can be performed first. The fact that this procedure works as expected, even in the presence of one or more $X$ errors, follows from the fact that $X$ gates on any of the nine qubits used for the encoding commute with all of the gates in our simplified circuit for measuring the syndrome for $Z$ errors. Thus, this syndrome measurement will still correctly identify which block has been affected by a $Z$ error. The fact that a $Z$ error on any block is corrected by applying a $Z$ gate to any qubit of that block, even if an $X$ error has also occurred, follows from the same argument as above concerning the ordering of $X$ and $Z$ gates giving us equivalent circuits up to a global phase.

It follows that the 9-qubit Shor code can correct an $X$ error, a $Z$ error, or both, on any one of the nine qubits used for this code. In fact, we can correct more errors than that, including multiple $X$ errors (as long as they fall into different blocks) or multiple $Z$ errors (as long as at most one block experiences an odd number of them) — but going forward, what will be most relevant for the purposes of this lesson is that we can correct an $X$ error, a $Z$ error, or both on any one qubit.

---

Error reduction for random errors

Before we move on to the last section of the lesson, which concerns arbitrary quantum errors, let's briefly consider the performance of the 9-qubit Shor code when errors represented by Pauli matrices occur randomly on the qubits.

To be more concrete, let's consider a simple noise model where errors occur independently on the qubits, with each qubit experiencing an error with probability $p$, and with no correlation between errors on different qubits — along similar lines to a binary symmetric channel for classical bits. We could assign different probabilities for $X,$ $Y,$ and $Z$ errors to occur, but to keep things as simple as possible, we'll consider the worst case scenario for the 9-qubit Shor code, which is that a $Y$ error occurs on each of the affected qubits. A $Y$ error, by the way, is equivalent (up to an irrelevant global phase factor) to both an $X$ and a $Z$ error occurring on the same qubit, given that $Y = iXZ.$ This explains our apparent disregard of $Y$ errors up to this point.

Now, supposing that $\mathsf{Q}$ is a qubit in some particular state that we'd like to protect against errors, we can consider the option to use the 9-qubit Shor code. A natural question to ask is, "Should we use it?"

The answer is not necessarily "yes." If there's too much noise, meaning in this context that $p$ is too large, using the Shor code could actually make things worse — just like the 3-bit repetition code is worse than no code when $p$ is larger than one-half. But, if $p$ is small enough, then the answer is "yes," we should use the code, because it will decrease the likelihood that the encoded state becomes corrupted. Let's see why this is, and what it means for $p$ to be too large or small enough for this code.

The Shor code corrects any Pauli error on a single qubit, including a $Y$ error of course, but it doesn't properly correct two or more $Y$ errors. To be clear, we're assuming that we're using the $X$ and $Z$ error corrections described earlier in the section. (Of course, if we knew in advance that we only had to worry about $Y$ errors, we would naturally choose our corrections differently — but that's cheating the noise model, and we'd always be able to change the model by selecting different Pauli errors to make this new choice of corrections fail whenever two or more qubits are affected by errors.)

So, the code protects $\mathsf{Q}$ so long as at most one of the nine qubits is affected by an error, which happens with probability

$$(1-p)^9 + 9 p (1-p)^8.$$

Otherwise, with probability

$$1 - (1-p)^9 - 9 p (1-p)^8,$$

the code fails to protect $\mathsf{Q}.$

Specifically, what that means in this context is that, up to a global phase, a non-identity Pauli operation will be applied to our qubit $\mathsf{Q}$ (as a logical qubit). That is, if $X$ and $Z$ errors are detected and corrected for the Shor code as described earlier in the lesson, we'll be left with the encoding of a state that's equivalent, up to a global phase, to the encoding of a non-identity Pauli operation applied to the original state of $\mathsf{Q}.$ A more succinct way to say this is that a logical error will have occurred. That may or may not have an effect on the original state of $\mathsf{Q}$ — or in other words the logical qubit we've encoded with nine physical qubits — but, for the sake of this analysis, we're considering this event to mean failure.

On the other hand, if we didn't bother to use the code, our one and only qubit would suffer a similar fate (of being subject to a non-identity Pauli operation) with probability $p.$ The code helps when the first probability is smaller than the second:

$$1 - (1-p)^9 - 9 p (1-p)^8 < p.$$

Here's a plot that illustrates, for very small values of $p,$ that the code provides an advantage, with the break-even point occurring at about $0.0323.$

If $p$ is smaller than this break-even point, then the code helps; at the break-even point the probabilities are equal, so we're just wasting our time along with 8 qubits if we use the code; and beyond the break-even point we should absolutely not be using this code because it's increasing the chance of a logical error on $\mathsf{Q}.$

Three and a quarter percent or so may not seem like a very good break-even point, particularly when compared to $50\%,$ which is the analogous break-even point for the 3-bit repetition code for classical information. This difference is, in large part, due to the fact that quantum information is more delicate and harder to protect than classical information. But also — while recognizing that the 9-qubit Shor code represents a brilliant discovery, as the world's first quantum error correcting code — it should be acknowledged that it isn't actually a very good code in practical terms.