# CSS codes are the only stabilizer codes with transversal CNOT?

Given a stabilizer code $$\mathcal{C}$$ then $$\mathcal{C} \text{ is CSS} \iff \text{CNOT} \text{ is transversal}.$$

The forward implication is well known, see for example Transversal logical gate for Stabilizer (or at least Steane code). On the other hand, Adam Zalcman claims in the comments in Small codes with transversal Hadamard that the reverse implication can be shown.

Can someone share a proof of this claim?

TL;DR: There are a few inequivalent ways to define the transversal construction for a logical gate. The precise statement of the relationship between transversal CNOT and the CSS codes depends on the choice of definition.

## Conventions

Suppose that $$\mathcal{C}$$ is an $$[\![n,k]\!]$$ stabilizer code. The subscript $$L$$ in $$U_L$$ will indicate operator $$U$$ acting on the code subspace. All operators without the subscript act on the Hilbert space of the physical qubits. We say that a Pauli operator is $$X$$-type if it is a tensor product of $$X$$ and identity. Similarly, for $$Z$$-type Pauli operators. I will implicitly use the tensor product with $$n$$ factors to act across the $$n$$ physical qubits making up the code block and the tensor product with two factors to act across the two logical code blocks involved in the logical CNOT.

## Definitions

Definition 1 If $$U^{\otimes n}$$ effects $$U_L$$ on the code subspace $$\mathcal{C}$$ then we say that $$U$$ is strictly transversal for $$\mathcal{C}$$.

Definition 2 If there exist operators $$V_i$$ with $$i=1,\dots,n$$ such that $$V=V_1\otimes\dots\otimes V_n$$ effects $$U_L$$ on the code subspace $$\mathcal{C}$$ then we say that $$U$$ is weakly transversal for $$\mathcal{C}$$.

Perhaps a better way to say "$$\mathcal{C}$$ has strictly transversal CNOT" is "CNOT broadcasts for $$\mathcal{C}$$" as Craig Gidney did in a comment below his answer. This is how I would say it succinctly now if I were to write the original comment again.

## Connection to CSS codes

Claim 1 The following conditions are equivalent

1. $$\mathcal{C}$$ is a CSS code.
2. $$\mathcal{C}$$ admits strictly transversal logical CNOT.

Sketch of proof for claim 1

The implication $$1\implies 2$$ is proved here. Let's prove $$2\implies 1$$. Suppose that $$g$$ is a stabilizer of $$\mathcal{C}$$ with $$g=i^ag_Xg_Z$$ where $$a\in\mathbb{Z}_4$$, $$g_X$$ is an $$X$$-type Pauli operator and $$g_Z$$ is a $$Z$$-type Pauli operator. Then $$g\otimes I$$ is a stabilizer of $$\mathcal{C}\otimes\mathcal{C}$$. But if CNOT is strictly transversal for $$\mathcal{C}$$, then $$g\otimes g_X$$ is a stabilizer of $$\mathcal{C}\otimes\mathcal{C}$$ and hence so is $$I\otimes g_X$$. In particular, $$I\otimes g_X$$ stabilizes every product state in $$\mathcal{C}\otimes\mathcal{C}$$. Therefore $$g_X$$ stabilizes $$\mathcal{C}$$. By analogous argument $$g_Z$$ stabilizes $$\mathcal{C}$$.

Thus, given a set $$\mathcal{G}$$ of generators for the stabilizer group $$\mathcal{S}$$ of $$\mathcal{C}$$ we can construct two sets $$\mathcal{G}_X$$ and $$\mathcal{G}_Z$$ such that $$\langle\mathcal{G}_X\cup\mathcal{G}_Z\rangle=\mathcal{S}$$ and every operator in $$\mathcal{G}_X$$ is an $$X$$-type Pauli operator and analogously for $$\mathcal{G}_Z$$. Finally, we choose an independent subset of $$\mathcal{G}_X\cup\mathcal{G}_Z$$. This set of generators splits into the $$X$$-sector and the $$Z$$-sector, so $$\mathcal{C}$$ is a CSS code.$$\square$$

This is the proof I had in mind in the comment. However, for completeness, note that there is a relationship between CSS codes and the other definition of transversal construction, although it is a little more complicated to state.

Claim 2 The following conditions are equivalent

1. $$\mathcal{C}$$ is equivalent to a CSS code under local unitary $$W=W_1\otimes\dots\otimes W_n$$.
2. $$\mathcal{C}$$ admits weakly transversal logical CNOT effected by $$V=V_1\otimes\dots\otimes V_n$$ where $$V_i=W_i^{\otimes 2}\circ\text{CNOT}\circ W_i^{\dagger\otimes 2}$$ for every $$i=1,\dots,n$$.

Sketch of proof for claim 2

First, suppose that $$\mathcal{C}=W\mathcal{D}$$ where $$W=W_1\otimes\dots\otimes W_n$$ and $$\mathcal{D}$$ is a CSS code. By Claim 1 above $$\text{CNOT}^{\otimes n}$$ effects logical CNOT on $$\mathcal{D}\otimes\mathcal{D}$$. But then $$V=(W_1^{\otimes 2}\circ\text{CNOT}\circ W_1^{\dagger\otimes 2})\otimes\dots\otimes(W_n^{\otimes 2}\circ\text{CNOT}\circ W_n^{\dagger\otimes 2})\tag1$$ effects CNOT on $$\mathcal{C}\otimes\mathcal{C}$$. This shows that $$1\implies 2$$.

Reversing the argument, assume that $$V$$ in $$(1)$$ effects CNOT on $$\mathcal{C}\otimes\mathcal{C}$$. But then $$W^{\dagger\otimes 2} VW^{\otimes 2}$$ effects CNOT on $$\mathcal{D}\otimes\mathcal{D}=(W^\dagger\otimes W^\dagger)\mathcal{C}\otimes\mathcal{C}$$. However, $$W^{\dagger\otimes 2} VW^{\otimes 2}=\text{CNOT}^{\otimes n}$$, so $$\mathcal{D}$$ is CSS by Claim 1. This shows that $$2\implies 1$$.$$\square$$

One way to look at these concepts and their relationships is to note that the strictly transversal construction derives its significance from its connection to the CSS codes, the weakly transversal construction derives its significance from its fault tolerant character and the equivalence under local unitaries connects the two constructions.

• Ok this is great and exactly what I was hoping for! Jun 1 at 13:21

The XZZX surface code isn't a CSS code but has a transversal CNOT.

The main caveat, which I haven't checked if it happens or not, is that the physical gates may include CZs and XCXs in addition to CNOTs. Regardless, the logical gate would still be transversal because it satisfies the property that it doesn't interact any physical qubits within a code block.

• The $XZZX$ surface code is locally equivalent to the conventional surface code which is CSS (see for example arxiv.org/abs/2009.07851). So I am guessing Zalcman meant that the theorem holds up to local equivalence. May 31 at 16:45
• @EricKubischta My guess is that he was using a stricter definition of "transversal" where you must exactly broadcast specifically the CNOT gate without any permutation between the two codes. I'll ask him. May 31 at 17:04
• +1 Unfortunately my original comment was ambiguous. XZZX code is a nice counterexample to the false interpretation of it. You are right that the source of ambiguity is the definition of "transversal". See Definition 1 and Claim 1 in my answer for the interpretation of the comment that works. Thanks for bringing this up! Jun 1 at 6:16