CSS Code in disguise

Question

Suppose I have a quantum error correcting code described by a set of stabilizers. Is there any easy way of checking whether or not it is equivalent to a code constructed using the CSS construction, using local Clifford transformations?

Answer 1

Yes. We will define a procedure for checking whether a given stabilizer code $\mathcal{G}$ is a Calderbank-Shor-Steane (CSS) code using the following

Theorem. Stabilizer code $\mathcal{G}$ is a CSS code if and only if $\mathcal{G}$ has transversal CNOT.

Proof sketch: Suppose $\mathcal{G}$ is a CSS code on $n$ qubits with stabilizer $S$. We can choose a set of stabilizer generators that splits into the X and Z sectors. In other words, we can select generators so that each is a tensor product of identity and Pauli $X$ operators ($X$-type generators) or identity and Pauli $Z$ operators ($Z$-type generators). Suppose $g_x\in S$ is an $X$-type stabilizer generator and $g_z\in S$ a $Z$-type stabilizer generator. Then we see that

$$ CNOT^{\otimes n} \circ (g_x \otimes I) \circ CNOT^{\otimes n} = g_x \otimes g_x \\ CNOT^{\otimes n} \circ (I \otimes g_x) \circ CNOT^{\otimes n} = I \otimes g_x \\ CNOT^{\otimes n} \circ (g_z \otimes I) \circ CNOT^{\otimes n} = g_z \otimes I \\ CNOT^{\otimes n} \circ (I \otimes g_z) \circ CNOT^{\otimes n} = g_z \otimes g_z $$

are all in $S \times S$. Therefore, transversal CNOT preserves the code subspace of the encoded control and target qubits.

Conversely, write $g\in S$ as $g = g_x g_z$ where $g_x$ is a tensor product of identity and Pauli $X$ operators and $g_z$ is a tensor product of identity and Pauli $Z$ operators. Calculate that

$$ CNOT^{\otimes n} \circ (g \otimes I) \circ CNOT^{\otimes n} = g \otimes g_x \\ CNOT^{\otimes n} \circ (I \otimes g) \circ CNOT^{\otimes n} = g_z \otimes g. $$

Therefore, if transversal CNOT preserves the code subspace then $g_x \in S$ and $g_z \in S$. Thus, we can split stabilizer generators into the $X$ and $Z$ sectors, so $\mathcal{G}$ is a CSS code. $\square$

You can also find the proof on p.16 of this paper. Our procedure for determining whether a given stabilizer code is a CSS code follows the second part of the proof above.

---

Procedure. For every stabilizer generator $g$ form the tensor products $g \otimes I$ and $I \otimes g$ and apply transversal CNOT

$$ CNOT^{\otimes n} \circ (g \otimes I) \circ CNOT^{\otimes n} = g \otimes g_x \\ CNOT^{\otimes n} \circ (I \otimes g) \circ CNOT^{\otimes n} = g_z \otimes g. $$

Next, verify that $g_x$ and $g_z$ belong to the stabilizer. If for any $g$, the corresponding $g_x$ or $g_z$ is not in the stabilizer then the code is not a CSS code. If for every $g$, both $g_x$ and $g_z$ are in the stabilizer, then it is a CSS code.

---

Remark on results. Note that the above procedure not only determines whether or not a stabilizer code is a CSS code, but also finds the stabilizer generators of the $X$ and $Z$ types. These generators determine the two classical codes used in the CSS construction of the code.

Remark on complexity. Note that checking membership in a group specified by $n$ generators scales exponentially with $n$. In practice, stabilizer groups are often small allowing exhaustive search or have symmetries that can be exploited to establish or rule out membership.

---

Example: 5-qubit Shor's code. The stabilizer generators are

$$ g_1 = XZZXI \\ g_2 = IXZZX \\ g_3 = XIXZZ \\ g_4 = ZXIXZ $$

(see for example Figure 10.12 on p.469 of Nielsen & Chuang). Calculate

$$ CNOT^{\otimes 5} \circ (g_1 \otimes IIIII) \circ CNOT^{\otimes 5} = g_1 \otimes XIIXI $$

which does not belong to the stabilizer by the following

Lemma. Every non-identity element of the stabilizer group of the 5-qubit Shor's code is a tensor product that includes exactly one identity operator.

Proof. Partition the fifteen non-identity elements of the group into disjoint subsets $A_k$ for $k=1, 2, 3, 4$ according to the minimum number of generators necessary to represent them. It is clear that the lemma is true for all $g \in A_1$. By examining pairs of generators above it is easy to see that it is also true for all $g \in A_2$. Now, $A_4 = \{ZZXIX\}$. Finally, by comparing each generator above against the sole member of $A_4$ we see that it is also true for $A_3$. $\square$.

Thus, we see that the 5-qubit Shor's code is not a CSS code. An alternative approach is to compute all sixteen elements of the stabilizer and verify that $XIIXI$ does not belong to it.

Incidentally we just showed that the 5-qubit Shor's code does not admit transversal CNOT gate.

Answer 2

If it were me, I'd write out the $k$ $N$-qubit stabilizer generators in a $k\times 2N$ binary matrix, where each row corresponds to a stabilizer generator, with the first $N$ bits being the positions of the $X$ rotations, and the second $N$ being the positions of the $Z$s.

A CSS code can be converted into a block structure where there are rows with only $X$ operations, and rows with only $Z$ operations, and no mixing. So you simply have the task of using row operations (modulo 2) to see if you can convert it into that form (a standard row reduction will get you about half way). If you cannot, the code is not a stabilizer code. If you can, then this instantly gives you the two classical codes that are used. One should probably check the required relations between parity check matrices, although I guess these will generally be satisfied.

Answer 3

Every $[[n,k,d]]$ stabilizer code can be mapped to a $[[4n,2k,2d]]$ CSS code. This may not be what you want if you want to keep $n$ fixed, but look at this paper for possible clues; it gives explicit mappings from one to the other (with fermionic codes as an intermediate step) : Majorana Fermion Codes https://arxiv.org/abs/1004.3791