Stabilizer codes

Now we'll define stabilizer codes in general. We'll also discuss some of their basic properties and how they work, including how states can be encoded and how errors are detected and corrected using these codes.

---

Definition of stabilizer codes

An $n$-qubit stabilizer code is specified by a list of $n$-qubit Pauli operations, $P_1,\ldots,P_r.$ These operations are called stabilizer generators in this context, and they must satisfy the following three properties.

1. The stabilizer generators all commute with one another.

   $$P_j P_k = P_k P_j \qquad \text{(for all $j,k\in\{1,\ldots,r\}$)}$$

2. The stabilizer generators form a minimal generating set.

   $$P_k \notin \langle P_1,\ldots,P_{k-1},P_{k+1},\ldots,P_r\rangle \qquad \text{(for all $k\in\{1,\ldots,r\}$)}$$

3. At least one quantum state vector is fixed by all of the stabilizer generators.

   $$-\mathbb{I}^{\otimes n} \notin \langle P_1,\ldots, P_r\rangle$$

   (It's not obvious that the existence of a quantum state vector $\vert\psi\rangle$ fixed by all of the stabilizer generators, meaning $P_1 \vert\psi\rangle = \cdots = P_r \vert\psi\rangle = \vert\psi\rangle,$ is equivalent to $-\mathbb{I}^{\otimes n} \notin \langle P_1,\ldots, P_r\rangle,$ but indeed this is the case, and we'll see why a bit later in the lesson.)

Assuming that we have such a list $P_1,\ldots,P_r,$ the code space defined by these stabilizer generators is the subspace $\mathcal{C}$ containing every $n$-qubit quantum state vector fixed by all $r$ of these stabilizer generators.

$$\mathcal{C} = \bigl\{ \vert\psi\rangle \,:\, P_1 \vert\psi\rangle = \cdots = P_r \vert\psi\rangle = \vert\psi\rangle \bigr\}$$

Quantum state vectors in this subspace are precisely the ones that can be viewed as valid encodings of quantum states. We'll discuss the actual process of encoding later.

Finally, the stabilizer of the code defined by the stabilizer generators $P_1, \ldots, P_r$ is the set generated by these operations:

$$\langle P_1,\ldots,P_r\rangle.$$

A natural way to think about a stabilizer code is to view the stabilizer generators as observables, and to collectively interpret the outcomes of the measurements associated with these observables as an error syndrome. Valid encodings are $n$-qubit quantum state vectors for which the measurement outcomes, as eigenvalues, are all guaranteed to be $+1.$ Any other syndrome, where at least one $-1$ measurement outcome occurs, signals that an error has been detected.

We'll take a look at several examples shortly, but first just a few remarks about the three conditions on stabilizer generators are in order.

The first condition is natural, in light of the interpretation of the stabilizer generators as observables, for it implies that it doesn't matter in what order the measurements are performed: the observables commute, so the measurements commute. This naturally imposes certain algebraic constraints on stabilizer codes that are important to how they work.

The second condition requires that the stabilizer generators form a minimal generating set, meaning that removing any one of them would result in a smaller stabilizer. Strictly speaking, this condition isn't really essential to the way stabilizer codes work in an operational sense — and, as we'll see in the next lesson, it does sometimes make sense to think about sets of stabilizer generators for codes that actually don't satisfy this condition. For the sake of analyzing stabilizer codes and explaining their properties, however, we will assume that this condition is in place. In short, this condition guarantees that each observable that we measure to obtain the error syndrome adds information about possible errors, as opposed to being redundant and producing results that could be inferred from the other stabilizer generator measurements.

The third condition requires that at least one nonzero vector is fixed by all of the stabilizer generators, which is equivalent to $-\mathbb{I}^{\otimes n}$ not being contained in the stabilizer. The need for this condition comes from the fact that it actually is possible to choose a minimal generating set of $n$-qubit Pauli operations that all commute with one another, and yet no nonzero vectors are fixed by every one of the operations. We're not interested in "codes" for which there are no valid encodings, so we rule out this possibility by requiring this condition as a part of the definition.

---

Examples

Here are some examples of stabilizer codes for small values of $n.$ We'll see more examples, including ones for which $n$ can be much larger, in the next lesson.

3-bit repetition code

The 3-bit repetition code is an example of a stabilizer code, where our stabilizer generators are $Z \otimes Z \otimes \mathbb{I}$ and $\mathbb{I} \otimes Z \otimes Z.$

We can easily check that these two stabilizer generators fulfill the required conditions. First, the two stabilizer generators $Z \otimes Z \otimes \mathbb{I}$ and $\mathbb{I} \otimes Z \otimes Z$ commute with one another.

$$(Z \otimes Z \otimes \mathbb{I})(\mathbb{I} \otimes Z \otimes Z) = Z \otimes \mathbb{I} \otimes Z = (\mathbb{I} \otimes Z \otimes Z)(Z \otimes Z \otimes \mathbb{I})$$

Second, we have a minimal generating set (rather trivially in this case).

$$\begin{aligned} Z \otimes Z \otimes \mathbb{I} \notin \langle\mathbb{I} \otimes Z \otimes Z\rangle & = \{\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, \mathbb{I} \otimes Z \otimes Z\}\\[1mm] \mathbb{I} \otimes Z \otimes Z \notin \langle Z \otimes Z \otimes \mathbb{I}\rangle & = \{\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, Z \otimes Z \otimes \mathbb{I}\} \end{aligned}$$

And third, we already know that $\vert 000\rangle$ and $\vert 111\rangle,$ as well as any linear combination of these vectors, are fixed by both $Z \otimes Z \otimes \mathbb{I}$ and $\mathbb{I} \otimes Z \otimes Z.$ Alternatively, we can conclude this using the equivalent condition from the definition.

$$-\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\notin \langle Z \otimes Z \otimes \mathbb{I}, \mathbb{I} \otimes Z \otimes Z\rangle = \{ \mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, Z\otimes Z\otimes\mathbb{I}, Z\otimes\mathbb{I}\otimes Z, \mathbb{I}\otimes Z\otimes Z \}$$

These conditions can be much more difficult to check for more complicated stabilizer codes.

Modified 3-bit repetition code

In the previous lesson, we saw that it's possible to modify the 3-bit repetition code so that it protects against phase-flip errors rather than bit-flip errors. As a stabilizer code, this new code is easy to describe: its stabilizer generators are $X \otimes X \otimes \mathbb{I}$ and $\mathbb{I} \otimes X \otimes X.$

This time the stabilizer generators represent $X\otimes X$ observables rather than $Z\otimes Z$ observables, so they're essentially parity checks in the plus/minus basis rather than the standard basis. The three required conditions on the stabilizer generators are easily verified, along similar lines to the ordinary 3-bit repetition code.

9-qubit Shor code

Here's the 9-qubit Shor code, which is also a stabilizer code, expressed by stabilizer generators.

$$\begin{gathered} Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z\\[1mm] X \otimes X \otimes X \otimes X \otimes X \otimes X \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\otimes X \otimes X \otimes X \otimes X \otimes X \otimes X \end{gathered}$$

In this case, we basically have three copies of the 3-bit repetition code, one for each of the three blocks of three qubits, as well as the last two stabilizer generators, which take a form reminiscent of the circuit for detecting phase flips for this code.

An alternative way to think about the last two stabilizer generators is that they take the same form as for the 3-bit repetition code for phase flips, except that $X\otimes X\otimes X$ is substituted for $X,$ which is consistent with the fact that $X\otimes X\otimes X$ corresponds to an $X$ operation on logical qubits encoded using the 3-bit repetition code.

Before we move on to other examples, it should be noted that tensor product symbols are often omitted when describing stabilizer codes by lists of stabilizer generators, because it tends to make them easier to read and to see their patterns. For example, the same stabilizer generators as above for the 9-qubit Shor code look like this without the tensor product symbols being written explicitly.

$$\begin{array}{ccccccccc} Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z\\[1mm] X & X & X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I}& X & X & X & X & X & X \end{array}$$

7-qubit Steane code

Here's another example of a stabilizer code, known as the 7-qubit Steane code. It has some remarkable features, and we'll come back to this code from time to time throughout the remaining lessons of the course.

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

For now, let's simply observe that this is a valid stabilizer code. The first three stabilizer generators clearly commute with one another, because $Z$ commutes with itself and the identity commutes with everything, and the situation is similar for the last three stabilizer generators. It remains to check that if we take one of the $Z$-stabilizer generators (i.e., one of the first three) and one of the $X$-stabilizer generators (i.e., one of the last three), then these two generators commute, and one can go through the 9 possible pairings to check that. In all of these cases, an $X$ and a $Z$ Pauli matrix always line up in the same position an even number of times, so the two generators will commute, just like $X\otimes X$ and $Z\otimes Z$ commute. This is also a minimal generating set, and it defines a nontrivial code space, which are facts left to you to contemplate.

The 7-qubit Steane code is similar to the 9-qubit Shor code in that it encodes a single qubit and allows for the correction of an arbitrary error on one qubit, but it requires only 7 qubits rather than 9.

5-qubit code

Seven is not the fewest number of qubits required to encode one qubit and protect it against an arbitrary error on one qubit — here's a stabilizer code that does this using just 5 qubits.

$$\begin{array}{ccccc} X & Z & Z & X & \mathbb{I} \\[1mm] \mathbb{I} & X & Z & Z & X \\[1mm] X & \mathbb{I} & X & Z & Z \\[1mm] Z & X & \mathbb{I} & X & Z \\[1mm] \end{array}$$

This code is typically called the 5-qubit code. This is the smallest number of qubits in a quantum error correcting code that can allow for the correction of an arbitrary single-qubit error.

One-dimensional stabilizer codes

Here's another example of a stabilizer code, though it doesn't actually encode any qubits: the code space is one-dimensional. It is, however, still a valid stabilizer code by the definition.

$$\begin{array}{cc} Z & Z \\[1mm] X & X \end{array}$$

Specifically, the code space is the one-dimensional space spanned by an e-bit $\vert\phi^+\rangle.$

Here's a related example of a stabilizer code whose code space is the one-dimensional space spanned by a GHZ state $(\vert 000\rangle + \vert 111\rangle)/\sqrt{2}.$

$$\begin{array}{cc} Z & Z & \mathbb{I} \\[1mm] \mathbb{I} & Z & Z \\[1mm] X & X & X \end{array}$$

---

Code space dimension

Suppose that we have a stabilizer code, described by $n$-qubit stabilizer generators $P_1,\ldots,P_r.$ Perhaps the very first question that comes to mind about this code is, "How many qubits does it encode?"

This question has a simple answer. Assuming that the $n$-qubit stabilizer generators $P_1, \ldots, P_r$ satisfy the three requirements of the definition (namely, that the stabilizer generators all commute with one another, that this is a minimal generating set, and that the code space is nonempty), it must then be that the code space for this stabilizer code has dimension $2^{n-r},$ so $n-r$ qubits can be encoded using this code.

Intuitively speaking, we have $n$ qubits to use for this encoding, and each stabilizer generator effectively "takes a qubit away" in terms of how many qubits we can encode. Note that this is not about which or how many errors can be detected or corrected, it is only a statement about the dimension of the code space.

For example, for both the 3-bit repetition code and the modified version of that code for phase-flip errors, we have $n=3$ qubits and $r=2$ stabilizer generators, and therefore these codes can each encode 1 qubit. For another example, consider the 5-qubit code: we have 5 qubits and 4 stabilizer generators, so once again the code space has dimension 2, meaning that one qubit can be encoded using this code. For one final example, the code whose stabilizer generators are $X\otimes X$ and $Z\otimes Z$ has a one-dimensional code space, spanned by the state $\vert\phi^+\rangle,$ which is consistent with having $n=2$ qubits and $r=2$ stabilizer generators.

Now let's see how this fact can be proved. The first step is to observe that, because the stabilizer generators commute, and because every Pauli operation is its own inverse, every element in the stabilizer can be expressed as a product

$$P_1^{a_1} \cdots P_r^{a_r},$$

where $a_1,\ldots,a_r\in\{0,1\}.$ Equivalently, each element of the stabilizer is obtained by multiplying together some subset of the stabilizer generators. Indeed, every stabilizer element can be expressed uniquely in this way, due to the condition that $\{P_1,\ldots,P_r\}$ is a minimal generating set.

Next, define $\Pi_k$ to be the projection onto the space of $+1$-eigenvectors of $P_k,$ for each $k\in\{1,\ldots,r\}.$ These projections can be obtained by averaging the corresponding Pauli operations with the identity operation as follows.

$$\Pi_k = \frac{\mathbb{I}^{\otimes n} + P_k}{2}$$

The code space $\mathcal{C}$ is the subspace of all vectors that are fixed by all $r$ of the stabilizer generators $P_1,\ldots,P_r,$ or equivalently, all $r$ of the projections $\Pi_1,\ldots,\Pi_r.$

Given that the stabilizer generators all commute with one another, the projections $\Pi_1,\ldots,\Pi_r$ must also commute. This allows us to use a fact from linear algebra, which is that the product of these projections is the projection onto the intersection of the subspaces corresponding to the individual projections. That is to say, the product $\Pi_1\cdots\Pi_r$ is the projection onto the code space $\mathcal{C}.$

We can now expand out the product $\Pi_1\cdots\Pi_r$ using the formulas for these projections to obtain the following expression.

$$\Pi_1\cdots\Pi_r = \biggl(\frac{\mathbb{I}^{\otimes n} + P_1}{2}\biggr)\cdots\biggl(\frac{\mathbb{I}^{\otimes n} + P_r}{2}\biggr) = \frac{1}{2^r}\sum_{a_1,\ldots,a_r \in \{0,1\}} P_1^{a_1}\cdots P_r^{a_r}$$

In words, the projection onto the code space of a stabilizer code is equal, as a matrix, to the average over all of the elements in the stabilizer of that code.

Finally, we can compute the dimension of the code space by using the fact that the dimension of any subspace is equal to the trace of the projection onto that subspace. Thus, the dimension of the code space $\mathcal{C}$ is given by the following formula.

$$\operatorname{dim}(\mathcal{C}) = \operatorname{Tr}(\Pi_1\cdots\Pi_r) = \frac{1}{2^r} \sum_{a_1,\ldots,a_r \in \{0,1\}} \operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r})$$

We can evaluate this expression by making use of a couple of basic facts.

• We have $P_1^0 \cdots P_r^0 = \mathbb{I}^{\otimes n}$ and therefore

  $$\operatorname{Tr}(P_1^{0}\cdots P_r^{0}) = 2^n.$$

• For $(a_1,\ldots,a_r) \neq (0,\ldots,0),$ the product $P_1^{a_1}\cdots P_r^{a_r}$ must be $\pm 1$ times a Pauli operation — but we cannot obtain $\mathbb{I}^{\otimes n}$ because this would contradict the minimality of the set $\{P_1,\ldots,P_r\},$ and we cannot obtain $-\mathbb{I}^{\otimes n}$ because the third condition on the stabilizer generators forbids it. Therefore, because the trace of every non-identity Pauli operation is zero, we obtain

  $$\operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r}) = 0.$$

The dimension of the code space is therefore $2^{n-r}$ as claimed:

$$\begin{aligned} \operatorname{dim}(\mathcal{C}) & = \frac{1}{2^r} \sum_{a_1,\ldots,a_r \in \{0,1\}} \operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r}) \\ & = \frac{1}{2^r} \operatorname{Tr}(P_1^{0}\cdots P_r^{0}) \\ & = 2^{n-r}. \end{aligned}$$

As an aside, we can now see that the assumption that $-\mathbb{I}^{\otimes n}$ is not contained in the stabilizer implies that the code space must contain at least one quantum state vector. This is because, as we've just verified, this assumption implies that the code space has dimension $2^{n-r},$ which cannot be zero. The converse implication happens to be trivial: if $-\mathbb{I}^{\otimes n}$ is contained in the stabilizer, then the code space can't possibly contain any quantum state vectors, because no nonzero vectors are fixed by this operation.

---

Clifford operations and encodings

Next, we'll briefly discuss how qubits can be encoded using stabilizer codes, but to do that we first need to introduce Clifford operations.

Clifford operations

Clifford operations are unitary operations, on any number of qubits, that can be implemented by quantum circuits with a restricted set of gates:

• Hadamard gates
• $S$ gates
• CNOT gates

Notice that $T$ gates are not included, nor are Toffoli gates and Fredkin gates. Not only are those gates not included in the list, but in fact, it's not possible to implement those gates using the ones listed here; they're not Clifford operations. Pauli operations, on the other hand, are Clifford operations because they can be implemented with sequences of Hadamard and $S$ gates.

That's a simple way to define Clifford operations, but it doesn't explain why they're defined like this or what's special about this particular collection of gates. The real reason Clifford operations are defined like this is that, up to global phase factors, the Clifford operations are precisely the unitary operations that always transform Pauli operations into Pauli operations by conjugation. To be more precise, an $n$-qubit unitary operation $U$ is equivalent to a Clifford operation up to a phase factor if, and only if, for every $n$-qubit Pauli operation $P,$ we have

$$U P U^{\dagger} = \pm Q$$

for some $n$-qubit Pauli operation $Q.$

(Note that it is not possible to have $U P U^{\dagger} = \alpha Q$ for $\alpha\notin\{+1,-1\}$ when $U$ is unitary and $P$ and $Q$ are Pauli operations. This follows from the fact that the matrix on the left-hand side of the equation in question is both unitary and Hermitian, and $+1$ and $-1$ are the only choices for $\alpha$ that allow the right-hand side to be unitary and Hermitian as well.)

It is straightforward to verify the conjugation property just described when $U$ is a Hadamard, $S,$ or CNOT gate. In particular, this is easy for Hadamard gates,

$$H X H^{\dagger} = Z, \qquad H Y H^{\dagger} = -Y, \qquad H Z H^{\dagger} = X,$$

and $S$ gates,

$$S X S^{\dagger} = Y, \qquad S Y S^{\dagger} = -X, \qquad S Z S^{\dagger} = Z.$$

For CNOT gates, there are 15 non-identity Pauli operations on two qubits to check. Naturally, they can be checked individually — but the relationships between CNOT gates and $X$ and $Z$ gates listed (in circuit form) in the previous lesson, together with the multiplication rules for Pauli matrices, offer a shortcut to the same conclusion.

Once we know this conjugation property is true for Hadamard, $S,$ and CNOT gates, we can immediately conclude that it is true for circuits composed of these gates — which is to say, all Clifford operations.

It is more difficult to prove that the relationship works in the other direction, which is that if a given unitary operation $U$ satisfies the conjugation property for Pauli operations, then it must be possible to implement it (up to a global phase) using just Hadamard, $S,$ and CNOT gates. This won't be explained in this lesson, but it is true.

Clifford operations are not universal for quantum computation; unlike universal sets of quantum gates, approximating arbitrary unitary operations to any desired level of accuracy with Clifford operations is not possible. Indeed, for a given value of $n,$ there are only finitely many $n$-qubit Clifford operations (up to phase factors). Performing Clifford operations on standard basis states followed by standard basis measurements also can't allow us to perform computations that are outside of the reach of classical algorithms — because we can efficiently simulate computations of this form classically. This fact is known as the Gottesman-Knill theorem.

Encoders for stabilizer codes

A stabilizer code defines a code space of a certain dimension, and we have the freedom to use that code space however we choose — nothing forces us to encode qubits into this code space in a specific way. It is always possible, however, to use a Clifford operation as an encoder, if we choose to do that. To be more precise, for any stabilizer code that allows $m$ qubits to be encoded into $n$ qubits, there's an $n$-qubit Clifford operation $U$ such that, for any $m$-qubit quantum state vector $\vert\phi\rangle,$ we have that

$$\vert\psi\rangle = U \bigl(\vert 0^{n-m} \rangle \otimes \vert \phi\rangle\bigr)$$

is a quantum state vector in the code space of our code that we may interpret as an encoding of $\vert\phi\rangle.$

This is good because Clifford operations are relatively simple, compared with arbitrary unitary operations, and there are ways to optimize their implementation using techniques similar to ones found in the proof of the Gottesman-Knill theorem. As a result, circuits for encoding states using stabilizer codes never need to be too large. In particular, it is always possible to perform an encoding for an $n$-qubit stabilizer code using a Clifford operation that requires $O(n^2/\log(n))$ gates. This is because every Clifford operation on $n$ qubits can be implemented by a circuit of this size.

For example, here's an encoder for the 7-qubit Steane code. It is indeed a Clifford operation, and as it turns out, this one doesn't even need $S$ gates.

---

Detecting errors

For an $n$-qubit stabilizer code described by stabilizer generators $P_1,\ldots, P_r,$ error detection works in the following way.

To detect errors, all of the stabilizer generators are measured as observables. There are $r$ stabilizer generators, and therefore $r$ measurement outcomes, each one being $+1$ or $-1$ (or a binary value if we choose to associate $0$ with $+1$ and $1$ with $-1,$ respectively). We interpret the $r$ outcomes collectively, as a vector or string, as a syndrome. The syndrome $(+1,\ldots,+1)$ indicates that no error has been detected, while at least one $-1$ somewhere within the syndrome indicates an error has been detected.

Suppose, in particular, that $E$ is an $n$-qubit Pauli operation, representing a hypothetical error. (We're only considering Pauli operations as errors, by the way, because the discretization of errors works the same way for arbitrary stabilizer codes as it does for the 9-qubit Shor code.) There are three cases that determine whether or not $E$ is detected as an error.

Error detection cases

1. The operation $E$ is proportional to an element in the stabilizer.

   $$E = \pm Q \; \text{for some}\; Q \in \langle P_1,\ldots,P_r\rangle$$

   In this case, $E$ must commute with every stabilizer generator, so we obtain the syndrome $(+1,\ldots,+1).$ This means that $E$ is not detected as an error.

2. The operation $E$ is not proportional to an element in the stabilizer, but it nevertheless commutes with every stabilizer generator.

   $$E\neq \pm Q\; \text{for} \; Q \in \langle P_1,\ldots,P_r\rangle, \;\text{but}\; E P_k = P_k E \;\text{for every}\; k\in\{1,\ldots,r\}$$

   This is an error that changes vectors in the code space in some nontrivial way. But, because $E$ commutes with every stabilizer generator, the syndrome is $(+1,\ldots,+1),$ so $E$ goes undetected by the code.

3. The operation $E$ anti-commutes with at least one of the stabilizer generators.

   $$P_k E = -E P_k \; \text{for at least one} \; k\in\{1,\ldots,r\}$$

   The syndrome is different than $(+1,\ldots,+1),$ so the error $E$ is detected by the code.

In the first case, the error $E$ is not a concern because this operation does nothing to vectors in the code space, except to possibly inject an irrelevant global phase: $E \ket{\psi} = \pm\ket{\psi}$ for every encoded state $\ket{\psi}.$ In essence, this is not actually an error — whatever nontrivial action $E$ may have happens outside of the code space — so it's good that $E$ is not detected as an error, because nothing needs to be done about it.

The second case, intuitively speaking, is the bad case. It's the anti-commutation of an error with a stabilizer generator that causes a $-1$ to appear somewhere in the syndrome, signaling an error, but that doesn't happen in this case. So, we have an error $E$ that does change vectors in the code space in some nontrivial way, but it goes undetected by the code. For example, for the 3-bit repetition code, the operation $E = X\otimes X\otimes X$ falls into this category.

The fact that such an error $E$ must change some vectors in the code space in a non-trivial way can be argued as follows. By the assumption that $E$ commutes with $P_1,\ldots,P_r$ but is not proportional to a stabilizer element, we can conclude that we would obtain a new, valid stabilizer code by including $E$ as a stabilizer generator along with $P_1,\ldots,P_r.$ The code space for this new code, however, has only half the dimension of the original code space, from which we can conclude that the action of $E$ on the original code space cannot be proportional to the identity operation.

For the last of the three cases, which is that the error $E$ anti-commutes with at least one stabilizer generator, the syndrome has at least one $-1$ somewhere in it, which indicates that something is wrong. As we have already discussed, the syndrome won't uniquely identify $E$ in general, so it's still necessary to choose a correction operation for each syndrome, which might or might not correct the error $E.$ We'll discuss this step shortly, in the last part of the lesson.

Distance of a stabilizer code

As a point of terminology, when we refer to the distance of a stabilizer code, we mean the minimum weight of a Pauli operation $E$ that falls into the second category above — meaning that it changes the code space in some nontrivial way, but the code doesn't detect this. When it is said that a stabilizer code is an $[[n,m,d]]$ stabilizer code, using double square brackets, this means the following:

1. Encodings are $n$ qubits in length,
2. the code allows for the encoding $m$ qubits, and
3. the distance of the code is $d.$

As an example, let's consider the 7-qubit Steane code. Here are the stabilizer generators for this code:

$$\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}$$

This code has distance 3, and we can argue this as follows.

First consider any Pauli operation $E$ having weight at most 2, and suppose this operation commutes with all six stabilizer generators. We will conclude that $E$ must be the identity operation, which (as always) is an element of the stabilizer. This will show that the distance of the code is strictly greater than 2. Suppose, in particular, that $E$ takes the form

$$E = P \otimes Q \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}$$

for $P$ and $Q$ being possibly non-identity Pauli matrices. This is just one case, and it is necessary to repeat the argument that follows for all of the other possible locations for non-identity Pauli matrices among the tensor factors of $E,$ but the argument is essentially the same for all of the possible locations.

The operation $E$ commutes with all six stabilizer generators, so it commutes with these two in particular:

$$\begin{gathered} Z \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes Z\\[1mm] X \otimes \mathbb{I} \otimes X \otimes \mathbb{I} \otimes X \otimes \mathbb{I} \otimes X \end{gathered}$$

The tensor factor $Q$ in our error $E$ lines up with the identity matrix in both of these stabilizer generators (which is why they were selected). Given that we have identity matrices in the rightmost 5 positions of $E,$ we conclude that $P$ must commute with $X$ and $Z,$ for otherwise $E$ would anti-commute with one of the two generators. However, the only Pauli matrix that commutes with both $X$ and $Z$ is the identity matrix, so $P = \mathbb{I}.$

Now that we know this, we can choose two more stabilizer generators that have an $X$ and a $Z$ in the second position from left, and we draw a similar conclusion: $Q = \mathbb{I}.$ It is therefore the case that $E$ is the identity operation.

So, there's no way for an error having weight at most 2 to go undetected by this code, unless the error is the identity operation (which is in the stabilizer and therefore not actually an error). On the other hand, there are weight 3 Pauli operations that commute with all six of these stabilizer generators, but aren't proportional to stabilizer elements, such as $\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes X\otimes X\otimes X$ and $\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes Z\otimes Z\otimes Z.$ This establishes that this code has distance 3, as claimed.

---

Correcting errors

The last topic of discussion for this lesson is the correction of errors for stabilizer codes. As usual, assume that we have a stabilizer code specified by n-qubit stabilizer generators $P_1, \ldots, P_r.$

The $n$-qubit Pauli operations, as errors that could affect states encoded using this code, are partitioned into equal-sized collections according to which syndrome they cause to appear. There are $2^r$ distinct syndromes and $4^n$ Pauli operations, which means there are $4^n/2^r$ Pauli operations causing each syndrome. Any one of these errors could be responsible for the corresponding syndrome.

However, among the $4^n/2^r$ Pauli operations that cause each syndrome, there are some that should be considered as being equivalent. In particular, if the product of two Pauli operations is proportional to a stabilizer element, then those two operations are effectively equivalent as errors.

Another way to say this is that if we apply a correction operation $C$ to attempt to correct an error $E,$ then this correction succeeds so long as the composition $CE$ is proportional to a stabilizer element. Given that there are $2^r$ elements in the stabilizer, it follows that each correction operation $C$ corrects $2^r$ different Pauli errors. This leaves $4^{n-r}$ inequivalent classes of Pauli operations, considered as errors, that are consistent with each possible syndrome.

This means that, unless $n=r$ (in which case we have a trivial, one-dimensional code space), we can't possibly correct every error detected by a stabilizer code. What we must do instead is to choose just one correction operation for each syndrome, in the hopes of correcting just one class of equivalent errors that cause this syndrome.

One natural strategy for choosing which correction operation to perform for each syndrome is to choose the lowest weight Pauli operation that, as an error, causes that syndrome. There may in fact be multiple operations that tie for the lowest weight error consistent with a given syndrome, in which case any one of them may be selected. The idea is that lower-weight Pauli operations represent more likely explanations for whatever syndrome has been measured. This might actually not be the case for some noise models, and one alternative strategy is to compute the most likely error that causes the given syndrome, based on the chosen noise model. For this lesson, however, we'll keep things simple and only consider lowest-weight corrections.

For a distance $d$ stabilizer code, this strategy of choosing the correction operation to be a lowest weight Pauli operation consistent with the measured syndrome always allows for the correction of errors having weight strictly less than half of $d,$ or in other words, weight at most $(d-1)/2.$ This shows, for instance, that the 7-qubit Steane code can correct for any weight-one Pauli error, and by the discretization of errors, this means that the Steane code can correct for an arbitrary error on one qubit.

To see how this works, consider the diagram below. The circle on the left represents all of the Pauli operations that result in the syndrome $(+1,\ldots,+1),$ which is the syndrome that suggests that no errors have occurred and nothing is wrong. Among these operations we have elements of the stabilizer (or operations that are proportional to elements of the stabilizer, to be more precise) and we also have non-trivial errors that change the code space in some way but aren't detected by the code. By the definition of distance, every Pauli operation in this category must have weight at least $d,$ because $d$ is defined as the minimum weight of these operations.

The circle on the right represents the Pauli operations that result in a different syndrome $s\neq(+1,\ldots,+1),$ including an error $E$ having weight strictly less than $d/2$ that we will consider.

The correction operation $C$ chosen for the syndrome $s$ is the lowest weight Pauli operation in the collection represented by the circle on the right in the diagram (or any one of them in case there's a tie). So, it could be that $C = E,$ but not necessarily. What we can say for certain, however, is that $C$ cannot have weight larger than the weight of $E,$ because $C$ has minimal weight among the operations in this collection — and therefore $C$ has weight strictly less than $d/2.$

Now consider what happens when the correction operation $C$ is applied to whatever state we obtained after the error $E$ takes place. Assuming that the original encoding was $\vert\psi\rangle,$ we're left with $CE\vert\psi\rangle.$ Our goal will be to show that $CE$ is proportional to an element in the stabilizer, implying that the correction is successful and (up to a global phase) we're left with the original encoded state $\vert\psi\rangle.$

First, because $E$ and $C$ cause the same syndrome, the composition $CE$ must commute with every stabilizer generator. In particular, if $P_k$ is any one of the stabilizer generators, then we must have

$$P_k E = \alpha E P_k \quad\text{and}\quad P_k C = \alpha C P_k$$

for the same value of $\alpha\in\{+1,-1\},$ because this is the $k$-th entry in the syndrome $s$ that both $C$ and $E$ generate. Hence, we have

$$P_k (CE) = \alpha C P_k E = \alpha^2 (CE) P_k = (CE) P_k,$$

so $P_k$ commutes with $CE.$ We've therefore shown that $CE$ belongs in the circle on the left in the diagram, because it generates the syndrome $(+1,\ldots,+1).$

Second, the composition $CE$ must have weight at most the sum of the weights of $C$ and $E$ — which follows from a moment's thought about products of Pauli operations — and therefore the weight of $CE$ is strictly less than $d.$ This implies that $CE$ is proportional to an element in the stabilizer of our code, which is what we wanted to show. By choosing our correction operations to be lowest-weight representatives of the set of errors that generate each syndrome, we're therefore guaranteed to correct any Pauli errors having weight less than half of the distance of the code.

There is one problem, however. For stabilizer codes in general, it's a computationally difficult problem to compute the lowest weight Pauli operation causing a given syndrome. (Indeed, this is true even for classical codes, which in this context we can think of as stabilizer codes where we only have $\mathbb{I}$ and $Z$ matrices appearing as tensor factors within the stabilizer generators.) So, unlike the encoding step, Clifford operations will not be coming to our rescue this time.

The solution is to choose specific codes for which good corrections can be computed efficiently, for which there's no simple recipe. Simply put, devising stabilizer codes for which good correction operations can be computed efficiently is part of the artistry of quantum code design. We'll see this artistry on display in the next lesson.