# Example stabilizer code which is not $GF(4)$ linear

In the paper

https://arxiv.org/abs/quant-ph/9704043

Eric Rains talks about $$GF(4)$$ linear codes and proves some of their properties, for example

• "many codes of interest (e.g., GF(4)-linear codes) are built out of distance 2 codes."

• "Since GF(4)-linear codes are built out of [[2n, 2(n−1), 2]]s, we find, for instance, that any equivalence between GF(4)-linear codes (subject to certain trivial restrictions) must lie in the Clifford group."

• "Corollary 14. Any equivalence of GF(4)-linear quantum codes lies in the Clifford group, unless the codes have minimum distance 1, or contain a codeword of weight 2."

• "Lemma 15. A GF(4)-linear code C is spanned by its minimal codewords."

• "Corollary 16. If Q is a GF(4)-linear code, then every automorphism of Q lies in the Clifford group."

I'm trying to better understand the limited scope of these results.

What is an example of a stabilizer code which is not $$GF(4)$$ linear?

Update: The comment from @unknown says that a CSS code is $$GF(4)$$ linear if and only if $$H_x=H_z$$. Now I'm curious if the $$[[5,1,3]]$$ code is $$GF(4)$$ linear.

• I would suspect that most qecc's do not correspond to GF(4) linear codes. Take the elements of GF(4) to be $(0,1,\omega,\omega^2)$, then GF(4) linearity means multiplying by $\omega$ takes a stabilizer to another stabilizer; this is very restrictive. If the code is a CSS code with $H_x$ different from $H_z$ then that would not be GF(4) linear...BTW GF(4) linear codes are easier to work with than GF(4) additive codes since you can borrow the full machinery of linear codes; additive codes are not as well structured. Apr 21 at 2:00
• @unknown Ok so the $[[4,2,2]]$ code and Steane $[[7,1,3]]$ code are both $GF(4)$ linear since they are CSS codes with $H_x=H_z$. Shor $[[9,1,3]]$ code and $[[15,1,3]]$ quantum Reed-Muller code are not $GF(4)$ linear because $H_x \neq H_z$. Is the $[[5,1,3]]$ code $GF(4)$ linear? Apr 21 at 12:40
• if $H_x \neq H_z$ then it's not linear; but it's not "if and only if". $[[5,1,3]]$ looks linear; at least with the choice of stabilizer generators I have. It's possible that linearity depends on the form of the generators. I'll put more details in an answer Apr 21 at 15:25
• @unknown I was just claiming it is an if and only if for the special case of CSS codes! Apr 21 at 15:56

Theorem 4 in https://arxiv.org/pdf/quant-ph/9608006.pdf says that linear $$GF(4)$$ codes are even. In particular this means that odd codes cannot be linear.

As an example, consider the $$[[5,1,2]]$$ CSS code given by stabilizer generators \begin{align*} ZZZZZ \\ XXXXI \\ IXXXX \\ XXIXX. \end{align*} This code is odd because the first generator has weight $$5$$. Note that one can easily check that there are no weight $$1$$ elements in the stabilizer.

If we use $$I \to 0$$, $$Z \to 1$$, $$X \to \omega$$, and $$Y \to \omega^2$$, then the stabilizer in $$GF(4)$$ is \begin{align*} 11111 \\ \omega \omega \omega \omega 0 \\ 0 \omega \omega \omega \omega \\ \omega \omega 0 \omega \omega. \end{align*} If we multiply the second generator by $$\omega$$ twice and use the fact that $$\omega^3 = 1$$ then we get the element $$11110$$. But that added with the first generator is $$00001$$. But we know there are no weight 1 elements in the stabilizer so this code is not closed under $$\omega$$ and hence it is not linear (as expected since it is odd).

More generally, for linear codes if $$g$$ is in the stabilizer then $$\omega g$$ and $$\omega^2 g$$ must also be in the stabilizer. But this is a sort of "Pauli cycle", e.g., $$\omega g$$ is just $$g$$ with each $$X$$ replaced by $$Y$$, each $$Y$$ replaced by $$Z$$, each $$Z$$ replaced by $$X$$ and each $$I$$ left alone (and $$\omega^2 g$$ is the same except in reverse order).

For example, the $$[[5,1,3]]$$ code has generators $$IIIII$$ and \begin{align*} (XZZXI)_\text{cyc} \\ (YXXYI)_\text{cyc} \\ (ZYYZI)_\text{cyc} \end{align*} where the subscript indicates all 5 cyclic shifts occur. This way of writing the stabilizer makes it clear that the code is linear because the 2nd line is just $$\omega$$ times the first and the 3rd line is just $$\omega^2$$ times the first.

Thus a linear $$GF(4)$$ code is a stabilizer code that is even and whose stabilizer is closed under "Pauli cycles".

Note there is also a restriction on $$n$$ and $$k$$. For an $$[[n,k,d]]$$ code, the stabilizer has size $$2^{n-k}$$. On the other hand, for linear codes, the size must be $$1 + 3 p$$ for some integer $$p$$. To be sure, the $$+1$$ comes from the identity and the $$3p$$ comes because each generator comes in a package of $$3$$ from the "Pauli cycles." Thus we must have $$1+3p = 2^{n-k}$$ or $$p = (2^{n-k}-1)/3$$. However, $$p$$ is an integer iff $$n-k$$ is even. It follows that linear codes must have $$n-k$$ even.

Then for example, linear stabilizer states $$[[n,0,d]]$$ can only occur when $$n$$ is even. Moreover, $$[[n,1,d]]$$ can only occur for $$n$$ odd.

For $$[[5,1,3]]$$ code :

stabilizers : [0,1,0,0,1, 0,0,1,1,0] ~ IXZZX

[[0,1,0,0,1,0,0,1,1,0],
[1,0,1,0,0,0,0,0,1,1],
[0,1,0,1,0,1,0,0,0,1],
[0,0,1,0,1,1,1,0,0,0]];


GF(4) form : [0,1,2,3] ~ [0,1,w,w^2]

[[0,1,2,2,1],
[1,0,1,2,2],
[2,1,0,1,2],
[2,2,1,0,1]]


the first matrix has GF(2) rank = 4; code size = 2^4 = 16

the second has GF(4) rank = 2 ; code size = 4^2=16

so the code is linear.

For $$[[15,1,3]]$$ RM code the two matrices are :

[[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1]];

[[1,0,1,0,1,0,1,0,1,0,1,0,1,0,1],
[0,1,1,0,0,1,1,0,0,1,1,0,0,1,1],
[0,0,0,1,1,1,1,0,0,0,0,1,1,1,1],
[0,0,0,0,0,0,0,1,1,1,1,1,1,1,1],
[2,0,2,0,2,0,2,0,2,0,2,0,2,0,2],
[0,2,2,0,0,2,2,0,0,2,2,0,0,2,2],
[0,0,0,2,2,2,2,0,0,0,0,2,2,2,2],
[0,0,0,0,0,0,0,2,2,2,2,2,2,2,2],
[0,0,2,0,0,0,2,0,0,0,2,0,0,0,2],
[0,0,0,0,2,0,2,0,0,0,0,0,2,0,2],
[0,0,0,0,0,2,2,0,0,0,0,0,0,2,2],
[0,0,0,0,0,0,0,0,2,0,2,0,2,0,2],
[0,0,0,0,0,0,0,0,0,2,2,0,0,2,2],
[0,0,0,0,0,0,0,0,0,0,0,2,2,2,2]];


the first matrix has GF(2) rank = 14; code size = 2^14 = 16384

the second has GF(4) rank = 10 ; code size = 4^10 = 1048576

so the code is not linear.