# CSS Code in disguise

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?

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.

• Thanks alot for the very helpful answer. I guess I wanted to know if there is a way to see if a code is equivalent to a CSS code, via local Clifford transformations. For example, I think there is no way of converting the 5-qubit code to a CSS code using local Clifford transformations. Jan 14, 2021 at 6:28
• Hm, IIUC, there is a unitary $U=U_1 \otimes \dots \otimes U_n$ with $U_k$ single-qubit Cliffords and you are given stabilizers $UgU^\dagger\dots$ of the "disguised" code and would like to find out whether the stabilizers $g\dots$ define a CSS code. Is this right? I suppose $U$ is unknown? Jan 14, 2021 at 19:28
• Unfortunately, the above "CNOT test" does not work in this case since it answers the question "does a given set of stabilizer generators define a CSS code?" and in general, $UgU^\dagger\dots$ is not CSS even if $g\dots$ is. A counterexample is the 7-qubit Steane code disguised by $H\otimes I^{\otimes 6}$ - the result is not CSS because it fails the "CNOT test". Jan 14, 2021 at 19:29
• Depending on your goals, you may be able to make things work by restricting allowable $U$ to a set $A$ different than all local Cliffords, such as the Pauli group or the set of logical operators. Also, simply making $A$ small may allow you to run exhaustive search trying the "CNOT test" for every possible $U$. Jan 14, 2021 at 19:41
• I've upvoted this answer before, but running into it again this morning impressed me all over again! Especially nice that it illustrates the idea with an example proving CNOT isn't transversal for 5 qubit code. +1! Jul 29, 2022 at 13:41

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.

• Hi, thanks for the anwer. This does not completely answer my question, since equivalence includes local unitary transformations. One can start with a CSS code, thenapply a hadamard operator to one of the qubits (i.e., conjugate all the stabilizers with $H\otimes I \otimes I \ldots$), to obtain a new code. The new code will not look like a CSS code, but it is equivalent to one. Your procedure doesn't appear to work for this case. Jan 14, 2021 at 6:04
• Fair point! An immediate fudge that occurs to me is the following: Mostly, you might consider restricting unitaries to Clifford operations (there's the whole issue of local unitary $\neq$ local clifford for graph states which suggests this is not quite good enough, but still...) if you're talking about an operation to map you from tensor products of Paulis to tensor products of Paulis. Moreover, to preserve error correcting properties, you want to compose the unitary from single-qubit operations. Jan 14, 2021 at 7:35
• But we know that $X$ gates and phase gates don't change the stabilizers (except for some irrelevant signs). So we only have to worry about Hadamard, whose job is only to switch columns. There's probably a better way to do it, but at worst you could check all $2^{N-1}$ possible assignments of which columns are $X$ operations and which are $Z$. Jan 14, 2021 at 7:35

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