2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – unknown
    Apr 21 at 2:00
  • $\begingroup$ @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? $\endgroup$ Apr 21 at 12:40
  • $\begingroup$ 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 $\endgroup$
    – unknown
    Apr 21 at 15:25
  • $\begingroup$ @unknown I was just claiming it is an if and only if for the special case of CSS codes! $\endgroup$ Apr 21 at 15:56

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.