Investigations on Automorphism Groups of Quantum Stabilizer Codes

This research was supported by the Stanford Undergraduate Research Institute in Mathematics (SURIM) program during the summer of 2021. The author would like to thank Dr. Pawel Grzegrzolka for coordinating the program. The author also thanks his mentor, Dr. Daniel Bump, for introducing him to the area of quantum error correction, and also for many helpful conversations and insightful suggestions. His idea of investigating “twisted automorphisms” (Definitions 2.6, 2.13) was particularly fruitful.

We give a very brief overview of classical error correction to serve as motivation for the constructions of quantum error correction theory, which will be presented in Section 1.2. First, recall that in classical computing, the basic unit of computation is the bit, which takes a state of either 0 or 1; i.e. an element of $\mathbb{F}_{2}$. Thus an $n$-bit state is just an element of $\mathbb{F}_{2}^{n}$.

The fundamental idea of classical error correction is repetition. In particular, if we want to transmit $k$ bits of information, we would repeat that information in such a way that it would be “hard” to confuse slight moderations of the encoded information with an encoding of a different $k$ bits of information. For instance, if we wanted to send the bits 0 and 1 through a somewhat noisy channel, we could instead send the 3-bit sequences 000 and 111, so that even if there is a 1-bit error, we could use a “majority rules” scheme to correct the error. As an explicit example, if we received 010, which is not a possible codeword, we could conclude with high probability that 000 was the intended message. In this manner, we are essentially embedding one bit into three by the identification of $\mathbb{F}_{2}^{1}$ with the 1-dimensional subspace $\{000,111\}$ in $\mathbb{F}_{2}^{3}$, so we call such a scheme a linear code. We will soon see how the same ideas apply in the quantum world, although there are some caveats.

Some notational remarks are in order. First, we will write vectors/states in boldface, instead of the bra-ket convention popular in physics. Second, we will not bother with normalizing the state $a\mathbf{0}+b\mathbf{1}$ of a qubit so that $\lvert a\rvert^{2}+\lvert b\rvert^{2}=1$, as that does not affect our discussion.

We will usually refer to such a space of $n$ qubits as $\mathbb{C}^{2^{n}}$.

The central idea of quantum error correction is to identify a $k$-qubit space with some $2^{k}$-dimensional linear subspace, called the codespace, of an $n$-qubit space, called the ambient space, where $n>k$. We will call states in the ambient $2^{n}$-dimensional space physical, and states in the $2^{k}$-dimensional codespace logical. For example, if we encode a one-qubit space into three qubits by the map $\mathbf{0}\mapsto\mathbf{000},\mathbf{1}\mapsto\bf{111}$, we may refer to the physical state $\bf{000}$ as “logical $\bf{0}$”, denoted $\mathbf{0}_{L}$.

In this formalism, errors will just be linear operators acting on the codespace. To have error-correcting properties, this codespace should be redundant in some sense, but there is an added difficulty in that we are not allowed to create repetitions of quantum states, as we might do in classical computing. This is the no-cloning theorem, as discussed in Theorem 1 of [5]. Therefore, this codespace should consist of highly entangled states—“redundancy without repetition”. Moreover, in general physical situations, one may encounter errors randomly affecting a single qubit, or a small number of qubits, of the ambient space. A good code allows such errors to be corrected.

We now state the quantum error-correction conditions as a “black box”. A full derivation can be found in Section 10.3 of [8].

Using Theorem 1.3, one can show that if a code $C$ corrects a set of errors $\{E_{i}\}$, then it also corrects any linear combination of the $E_{i}$. This is an extremely powerful observation, because instead of possibly having to correct a continuum of errors, it now suffices to focus only on correcting a discrete set of error operations that span the full set of errors we want to correct. Because of this observation, it makes sense to introduce the Pauli matrices:

We call $X$ the bit flip operator, since it sends $\bf{0}$ to $\bf{1}$ and vice versa. Similarly, we call $Z$ the phase flip operator, since it sends $\bf{0}$ to itself, but $\bf{1}$ to $-\bf{1}$. Finally, $Y$ is a combined bit-phase operator, with an extra factor of $i$ thrown in to make the mathematics easier. The Pauli matrices act on the one-qubit space $\mathbb{C}^{2}$, but $n$-fold tensor products of them act on an $n$-qubit space in the natural way. For example, the tensor product $X\otimes Z\otimes I$ acts on $\mathbb{C}^{2^{3}}$ by sending $\bf{000}$ to $\bf{100}$, $\bf{111}$ to $-\bf{011}$, etc. In the rest of this paper, we will simply write tensor products of Pauli matrices as concatenations, so that the above $X\otimes Z\otimes I$ operator is simply $XZI$.

The Pauli matrices have remarkable properties that will be fully exploited in the rest of the paper. First, they are all both unitary and Hermitian, and they form a basis of the 2-by-2 complex matrices. So by the discussion after Theorem 1.3, if we wanted to, for instance, correct arbitrary errors occurring on the first qubit of a three-qubit system, we simply need to correct the errors $XII$, $ZII$, and $YII$ (along with $III$, which is automatic). Second, all of the Pauli matrices square to the identity, and they all commute or anticommute. In particular, two Pauli matrices anticommute if and only if they are different nonidentity matrices. This implies that the Pauli matrices form a projective representation of the four-group $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$, which is why they are chosen as our basis of the 2-by-2 complex matrices. Since complex scalars, in general, do not concern us, the fact that the Pauli matrices act like the elements of $\mathbb{Z}_{2}\times\mathbb{Z}_{2}$ is of great utility.

Now, although the quantum error-correction condition 1 is easy to verify for any particular code and set of errors, it is difficult to actually construct a code correcting a given set of error operations, particularly if that set is large. Indeed, we are usually interested in correcting sets of errors such as “all one-qubit errors,” which necessitates correcting an error set of size $3n$ if the ambient space is an $n$-qubit space (we need to correct an $X$, $Z$, and $Y$ error at each physical qubit). The stabilizer formalism introduced by Gottesman [4] provides a convenient workaround to this problem.

Note that the elements of $G_{1}$ are just Pauli matrices multiplied by some phase factor, which is a fourth root of unity. All elements in $G_{1}$ square to plus or minus the identity, and all elements commute or anticommute. This means that $G_{1}$ is “almost” an elementary abelian 2-group: its commutator subgroup is $\langle-I\rangle$, and $G_{1}/[G_{1},G_{1}]$ is indeed an elementary abelian 2-group of order $2^{2n+1}$. It will also be useful to speak of $G_{1}$ mod its center $Z(G_{1})=\langle iI\rangle$, so that we can consider elements without worrying about scalar multiples. We denote $G_{1}/Z(G_{1})$ by $P_{1}$.

It is natural to generalize the Pauli group to $n$-fold tensor products:

Again, $[G_{n},G_{n}]=\langle-I\rangle$, $G_{n}/[G_{n},G_{n}]$ is an elementary abelian 2-group, and $Z(G_{n})=\langle iI\rangle$. We denote $G_{n}/Z(G_{n})$ by $P_{n}$.

Before moving on to stabilizer codes, we mention an extremely useful way of writing elements of $P_{n}$, known as the check matrix. We see that an element $s\in P_{n}$ can uniquely be written as

$$X^{a_{1}}Z^{b_{1}}\otimes X^{a_{2}}Z^{b_{2}}\otimes\ldots\otimes X^{a_{n}}Z^{b_{n}},$$

where the $a_{i},b_{i}$ are 0 or 1. Therefore we represent $s$ as

$$(a|b)=\left[\begin{array}[]{cccc|cccc}a_{1}&a_{2}&\ldots&a_{n}&b_{1}&b_{2}&\ldots&b_{n}\end{array}\right],$$

(3)

which can be thought of as a vector in $\mathbb{F}_{2}^{2n}$. For example, the element $IXYZ$ is represented as

$$\left[\begin{array}[]{cccc|cccc}0&1&1&0&0&0&1&1\\ \end{array}\right].$$

The utility of this representation becomes clear when we define a symplectic bilinear form over $\mathbb{F}_{2}^{2n}$ given by

$$\langle(a|b),(c|d)\rangle=a\cdot d+b\cdot c,$$

(4)

where $\cdot$ is the usual dot product in $\mathbb{F}_{2}^{n}$. Then it is straightforward to check that if $s,s^{\prime}\in P_{n}$ have check matrix representations $(a|b)$, $(a^{\prime}|b^{\prime})$ respectively, $s$ and $s^{\prime}$ commute if and only if $\langle(a|b),(a^{\prime}|b^{\prime})\rangle=0$. Since $P_{n}$ is simply $G_{n}$ modded out by its center, the same is true for any lifts of $s,s^{\prime}$ to elements in $G_{n}$. The check matrix representation gives us a compact way of writing set of elements in $G_{n}$ or $P_{n}$, which will be useful later on.

We are now ready to define stabilizer codes. The key is to consider the action of $G_{n}$ on $\mathbb{C}^{2^{n}}$, and consider the fixed points of a subgroup of $G_{n}$.

It is easy to check that $C(S)$ is a subspace of the ambient space.

It is important to make a few remarks regarding this definition. First, $C(S)$ must contain all vectors in $\mathbb{C}^{2^{n}}$ that are fixed by everything in $S$. In particular, for a code $C^{\prime}$ to be called a stabilizer code, there must be some abelian subgroup $S$ of $G_{n}$, not containing $-I$, such that $C^{\prime}=C(S)$. It is not enough for $C^{\prime}\subset C(S)$. Second, we do not want $S$ to contain $-I$. Otherwise, if $-I\in S$, then for any $v\in C(S)$, we have $v=-Iv\Rightarrow v=0$, so that $C(S)$ is trivial. Similarly, we require $S$ to be abelian: if $s,s^{\prime}\in S$ do not commute, then they must anticommute, so that for any $v\in C(S)$, we have $v=(ss^{\prime})v=(-s^{\prime}s)v=-(s^{\prime}sv)=-v\Rightarrow v=0$. Note that because elements in $G_{n}$ either square to $I$ or $-I$, these two conditions imply that $S$ is an elementary abelian 2-group. Also, elements in $S$ may only have a scalar factor of plus or minus 1, lest they square to $-I$.

Given the construction of stabilizer codes, we would like to somehow connect a stabilizing subgroup $S\subset G_{n}$ with the dimension of $C(S)$, as well as with the errors that $C(S)$ can correct. Let us first answer the former question. First, note that $S$ can have size at most $2^{n}$. To see why, suppose $S$ has $m$ independent generators (so $\lvert S\rvert=2^{m}$), which we write in the check matrix format. We may think of $S$ as an $m$-dimensional subspace of the $\mathbb{F}_{2}$-vector space $\mathbb{F}_{2}^{2n}$. Because these generators all commute, $S$ is self-orthogonal with respect to the bilinear form in 4; that is, $S\subseteq S^{\perp}$. But $\dim S+\dim S^{\perp}=2n$, so that $m=\dim S\leq n$.

With $m\leq n$ in mind, it now makes sense to state the following proposition:

In this situation, we call $C$ an $[[n,k]]$ code, where the double brackets are meant to distinguish the quantum code $C$ from classical codes. From now on, $S$ will always be assumed to an abelian subgroup of $G_{n}$ not containing $-I$, and we will just write $C$ for $C(S)$ if there is no ambiguity in the stabilizing subgroup $S$.

We now discuss the error-correcting properties of $C$. First, we need to define a slight abuse of notation:

The idea behind this definition is that we can and should disregard the scalar phase of any element of $G_{n}$, since we know that if $C$ corrects some error $E$, it corrects any scalar multiple of $E$. Notice that $N(S)$ is equal to the centralizer of $S$, since two elements of $G_{n}$ either commute or anticommute, and $-I\not\in S$.

Along with this definition, we must reinterpret the quantum error-correction conditions, Theorem 1.3, in the language of stabilizer codes.

The criterion in Theorem 1.10 is much easier to use than that in Theorem 1.3. Instead of having to construct the projection matrix onto our code and do various matrix calculations, the error-correcting properties of a stabilizer code can be computed only using knowledge of $G_{n}$. Because of this, we introduce a few more definitions regarding elements of $G_{n}$ and $P_{n}$:

For instance, the element $XZIIZ\in P_{5}$ has weight 3, since it has three non-identity tensor factors.

From these definitions, we see that the product of any two weight $w$ operators has weight at most $2w$, and that the conjugate transpose does not change the weight of an operator. Then it follows from Theorem 1.10 that any code with distance greater than $2w$ can correct errors affecting any $w$ qubits.

More examples of small stabilizer codes, as well as more details about their theory, can be found in Section 10.5 of [8]. Many more examples of stabilizer codes, including codes with larger parameters $[[n,k,d]]$, can be found at [6]. We will reference those tables of quantum codes in the below sections.

Just like in the theory of classical codes, we can define the automorphism group of a QECC:

We are particularly interested in the case where $C$ is a stabilizer code with stabilizing subgroup $S$. Indeed, in this case we may also consider the action of $S_{n}$ on $G_{n}$ given by permuting tensor factors. This action is equivalently given by $\sigma(g)=M_{\sigma}gM_{\sigma}^{-1}$, where $g\in G_{n}$ and $M_{\sigma}^{-1}$ is the permutation matrix associated to $\sigma$ in the natural basis of $\mathbb{C}^{2^{n}}$. Then the above condition for $\operatorname{Aut_{strong}}(C)$ can be rephrased in terms of $S$:

Since all $\sigma\in S_{n}$ act as invertible linear maps on $S$, we can simplify the result of Proposition 2.2 to a form that is more suitable for actually computing strong automorphism groups.

It turns out that the notion of “strong automorphism group” does not produce many interesting examples for stabilizer codes with small $n$; in particular, it seems that for most codes, the strong automorphism group is usually small compared to the full symmetric group. We will see more examples in Section 2.2, and we will give some reasons as to why this general heuristic might be true in Section 3. Therefore we now introduce an extension of the automorphism group concept.

That is, $\sigma(C)$ is “almost” $C$, where we allow a twist of the vectors in $C$ by some element $\gamma_{\sigma}$ of the Pauli group (which is allowed to vary depending on $\sigma$, and is not necessarily unique). We should check that $\operatorname{Aut_{weak}}(C)$ is actually a group. Indeed this is the case, since we can view $\operatorname{Aut_{weak}}(C)$ as a semidirect product of sorts: if $\sigma,\tau\in\operatorname{Aut_{weak}}(C)$ correspond to $\gamma_{\sigma},\gamma_{\tau}\in G_{n}$, then

$$\sigma\tau(C)=(\sigma(\gamma_{\tau})\cdot\gamma_{\sigma})\cdot C,$$

(10)

as can be easily verified. Recall that the action of $\sigma$ on $G_{n}$ by permuting tensor factors is the same as the matrix action by conjugation, $g\mapsto M_{\sigma}gM_{\sigma}^{-1}$. Hence $\sigma\tau\in G_{n}$, since we can set $\gamma_{\sigma\tau}=\sigma(\gamma_{\tau})\cdot\gamma_{\sigma}$.

We now want to somewhat justify the labels “strong automorphism” and “weak automorphism”. In Proposition 2.2, we were able to give a characterization of strong automorphisms in terms of the stabilizing subgroup of a stabilizer code. We can do the same for weak automorphisms:

This somewhat justifies the “strong” and “weak” labels, since Propositions 2.2 and 2.7 show that a strong automorphism of $C(S)$ sends $S$ to itself, while a weak automorphism sends $S$ to itself but “disregarding signs”. Of course the strong automorphism group is a subgroup of the weak automorphism group.

This example shows that this weaker notion of automorphism can enlarge the strong automorphism group, and we will see in some later examples that $\operatorname{Aut_{weak}}(C)$ can be quite a bit larger than $\operatorname{Aut_{strong}}(C)$ for certain stabilizer codes $C$. This example also shows that $\operatorname{Aut_{strong}}(C)$ is not necessarily normal in $\operatorname{Aut_{weak}}(C)$. So we may pose the following (somewhat vague) question:

We extend the notion of an automorphism group one last time. For this, we need to introduce the (one-qubit) Clifford group $L_{1}$, following the terminology of [1] and [2].

In the terminology of quantum logic gates, $H$ is the Hadamard gate, and $S$ is the phase shift gate where the shift is by $\frac{\pi}{4}$. Note that the conjugation actions of $H$ and $S$ on $X$, $Y$, and $Z$ are as follows:

$HXH^{-1}=Z$	$SXS^{-1}=Y$
$HZH^{-1}=X$	$SZS^{-1}=Z$
$HYH^{-1}=-Y$	$SYS^{-1}=-X$

.

We can extend the action of $L_{1}$ on $G_{1}$ to $n$ qubits as follows, which gives us our second weakening of the strong automorphism group:

$L_{n}$ has a natural conjugation action on $G_{n}$, which motivates the following definition.

Since $L_{n}$ contains $G_{n}$, we have the chain of inclusions $\operatorname{Aut_{Clif}}(C)\supseteq\operatorname{Aut_{weak}}(C)\supseteq\operatorname{Aut_{strong}}(C)$ for a stabilizer code $C$. We are somewhat justified in calling $\operatorname{Aut_{Clif}}(C)$ an automorphism group: it is a group for the same reason that $\operatorname{Aut_{weak}}(C)$ is a group, and because the elements of $L_{n}$ act as automorphisms of $G_{n}$, it is not hard to show that if $\sigma\in\operatorname{Aut_{Clif}}(C)$, then $C$ and $\sigma(C)$ have the same $[[n,k,d]]$ parameters.

To aid computation, we make some useful observations involving Definition 2.13. First, if $g_{1},\ldots,g_{m}$ generate $S$, then for $\sigma$ to be in $\operatorname{Aut_{Clif}}(C)$ it suffices to verify that $\sigma(g_{i})\in\lambda_{\sigma}S\lambda_{\sigma}^{-1}$ for each $g_{i}$. This can be further weakened: it suffices that plus or minus $\sigma(g_{i})$ is in $\lambda_{\sigma}S\lambda_{\sigma}^{-1}$, since if we are only off by a sign, we can simultaneously correct for that by conjugating by an appropriate element of $G_{n}$, as in the proof of Proposition 2.7. Finally, because we can disregard signs, we can interpret the action of $L_{1}$ on $G_{1}$ (or each tensor factor of $G_{n}$) as $S_{3}$ acting on the non-identity Pauli matrices. For instance, the above table shows that $H$ induces the permutation $(XZ)$ and $S$ induces the permutation $(XY)$ on the set $\{X,Y,Z\}$, and various combinations of $H$ and $S$ induce the other permutations of $S_{3}$. So we can rephrase Definition 2.13 in a more verbose, but more intuitive, manner:

Note that we use $\cdot$ to emphasize the fact that $\sigma$ and $\rho_{\sigma}$ have very different actions: $\sigma$ permutes the tensor factors in each element, while $\rho_{\sigma}$ permutes $X$, $Y$, and $Z$ in each tensor factor.

Let us use Corollary 2.14 in an example. Recall from Remark 2.5 that if $C$ is the stabilizer code corresponding to the subgroup $S\subset G_{4}$ generated by $XXZZ$ and $YYXX$, then $\operatorname{Aut_{strong}}(C)=\{(1),(12),(34),(12)(34)\}\cong\mathbb{Z}_{2}\times\mathbb{Z}_{2}$. Using Corollary 2.8, it is easy to see that $\operatorname{Aut_{weak}}(C)$ is the same group. However, we now show that $\operatorname{Aut_{Clif}}(C)$ is the full $S_{4}$.

In this section we give many examples of $\operatorname{Aut_{strong}}(C),\operatorname{Aut_{weak}}(C)$, and $\operatorname{Aut_{Clif}}(C)$ for various small stabilizer codes $C$ with large distance. Most codes will be taken from [6]. The majority of these examples were calculated by hand and then verified using a SAGE program (see Appendix A). These hand calculations are somewhat tedious ad hoc processes, so we will only try to give a general outline of how they were done. We will also make some observations about the more noteworthy automorphism groups. However, we should again remark that the automorphism groups of a stabilizer code cannot be completely determined by the parameters $[[n,k,d]]$, so these examples should be taken as interesting specific cases rather than showcasing a general phenomenon.