# Equivalent $[\![n,k,d]\!]$ codes and transversal gates

An operator on the Hilbert space of $$n$$ qubits is called a local unitary if it is of the form $$U=\bigotimes_{i=1}^n g_i$$ where each $$g_i$$ is a $$2 \times 2$$ unitary matrix. In other words if it is an element of the group of local unitaries $$\bigotimes_{i=1}^n U_2$$ The group of all non-entangling gates on an $$n$$ qubit Hilbert space is exactly the normalizer of the group of local unitaries $$N \Bigg( \bigotimes_{i=1}^n U_2 \Bigg) \cong \bigotimes_{i=1}^n U_2 \rtimes S_n$$ The structure of this group as a subgroup of $$U_{2^n}$$ is a bit difficult to describe. Fortunately, in quantum mechanics global phase is irrelevant so we really work in a projective Hilbert space and the operations are projection unitaries. So modding everything out by a $$U_1$$ group of global phases the group of local projective unitaries as a subgroup of $$PU_{2^n}$$ becomes $$\prod_{i=1}^n PU_2$$ and it turns out the group of all non-entangling gates in $$PU_{2^n}$$ is exactly $$N \Bigg(\prod_{i=1}^n PU_2 \Bigg)= \Bigg(\prod_{i=1}^n PU_2 \Bigg) \rtimes S_n$$ where the symmetric group on $$n$$ letters acts by permuting the $$n$$ many $$PU_2$$ groups in the direct product in the natural way.

$$2$$ is not special in this discussion and can be replaced with any qudit dimension $$d$$.

Now we define code equivalence, following Raines

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

Two codes are locally equivalent if they are related by a local unitary. And we will say two codes are globally equivalent, or just equivalent, if they are related by a local unitary and a permutation (in other words, they are related by a non-entangling gate).

Let $$C_1,C_2$$ be two codes with the same parameters $$[\![n,k,d]\!]$$. Is it true that that $$C_1$$ and $$C_2$$ are equivalent if and only if they have isomorphic transversal gate groups?

Note that two codes which are equivalent must have conjugate and thus isomorphic transversal gate group.

Two $$[\![n,k,d[\!]$$ codes with the same transversal gates may be inequivalent under local unitaries.

## Example 1: Shor's $$9$$-qubit code and $$3\times 3$$ surface code

The $$9$$-qubit Shor's code and the $$3\times 3$$ rotated surface code are $$[\![9,1,3]\!]$$ codes with the single-qubit$$^1$$ transversal$$^2$$ group isomorphic to the Pauli group. However, they are not equivalent under local unitaries. We can see this by considering the number of stabilizers of a given weight which is an invariant of equivalence under local unitaries. We count nine weight-$$2$$ stabilizers in the stabilizer group of the $$9$$-qubit code but only four in the stabilizer group of the $$3\times 3$$ surface code.

## Example 2: Two different surface codes

Consider the rotated surface code on a $$2\times 4$$ lattice of data qubits and the surface code obtained by removing a corner data qubit in the $$3\times 3$$ rotated surface code. Both are $$[\![8, 1, 2]\!]$$ codes with the same set of transversal gates. They are inequivalent under local unitaries since they have different code distances for $$X$$ and $$Z$$ errors. The former has code distances two and four. The latter has code distances two and three.

## More examples: deforming topological codes, CSS construction

The case of two surface codes above suggests a way to obtain further examples by deforming topological codes, such as the surface code or the color code, so that they have the same code parameters but different shape.

Another approach would be to find two sufficiently different self-dual doubly even classical codes with the same parameters $$[n,k,d]$$ and apply the CSS construction. The resulting codes will admit transversal implementation to all Clifford gates.

$$^1$$ I'm assuming single-qubit gates to ensure group operation is well-defined. Nevertheless, I think the codes probably have the same two-qubit transversal gates as well. In particular, they are both CSS codes so CNOT can be implemented transversally in both. If these limitations of the first example are a concern, see the second example.
$$^2$$ Here, I have chosen to interpret "transversal" in the strict sense where we demand that the logical operator leaves the code subspace unchanged. If we allow code subspace deformation then the transversal group becomes larger, e.g. the Hadamard is weakly transversal in both the surface code and the $$9$$-qubit code.

• I of course remember your very thorough proof that the only transversal gates of the 9-qubit Shor code are the transversal Paulis quantumcomputing.stackexchange.com/questions/27157/…. Could you say more about why the $3 \times 3$ rotated surface code also only has transversal Paulis as its transversal gates? Oct 19, 2022 at 13:37
• Unfortunately, that answer had an error (It is true that $UgU^\dagger\in\mathcal{S}$ for all stabilizers $g$ implies that $U$ is a logical operator, but I used the converse which is false; we only have that $UgU^\dagger = U_L\oplus U_N$ where unitary $U_L$ maps the logical subspace to itself; this is actually rather important since it's why codes with transversal non-Cliffords exist). I rewrote it to fix the issue, so please have another look there. Apologies for the mistake. Oct 19, 2022 at 18:29
• Regarding the transversal gates of the surface code, I'm relying here on what seems to be fairly common knowledge, but admittedly, I don't know how to prove it at the moment (it would make a great QCSE question!). That's why I included the other examples and suggestions. BTW, it seems that a simple yet rigorous non-equivalence proof might be constructed for two color codes or two CSS codes deriving from self-dual doubly even classical codes (since in those cases the transversal group coincides with the Cliffords and we can appeal to Eastin-Knill theorem to rule out other transversal gates). Oct 19, 2022 at 18:32
• Ya, putting all my cards on the table here the counterexample I was definitely fishing for was two self dual doubly even CSS codes with the same parameters but that are not equivalent by local unitaries. That I would be very very very interested to see. If you can find that example I'll write you a thank you haiku. And just to clarify the common knowledge surface code thing, are saying that it is known that the $3 \times 3$ rotated surface code has only Paulis transversal? Or are you saying more generally that its known all surface codes have only Paulis transversal? Oct 19, 2022 at 18:42
• Hehe, I see. Well, a very simple example would be the following two $[\![14, 2, 3]\!]$ CSS codes. First code: use Steane code to encode the first logical qubit into physical qubits $1\dots 7$ and the second logical qubit into $8\dots 14$. Second code: use Steane code to encode the first logical qubit into physical qubits $1, 3, 5, 7, 9, 11, 13$ and the second logical qubit into $2, 4, 6, 8, 10, 12, 14$. In both codes, Cliffords are of course transversal. Oct 20, 2022 at 7:00

I'm not sure if this example deals quite with your intent, but I believe it answers the question...

Consider the [[15,1,3]] Reed-Muller code. This has transversal X,Z,S,T,cNOT, controlled-S, controlled-Z, controlled-controlled-Z but not H in its standard presentation (there are many more Z stabilizers than X stabilizers).

If I apply Hadamard to every qubit, I still have a [[15,1,3]] code, but the transversal operators are Hadamarded versions of the previous ones. This is clearly not the same group (I guess that if you put the two groups together, you'd have universality).

• I'll go back and clarify my question. I really mean isomorphic group when I say "the same group" (bad word choice on my part). As you note here and as I note in the last sentence of my question you can always apply a locally unitary $U$ ($U=H^{\otimes 15}$ here ) to some code $C_1$ ($C_1=[[15,1,3]]$ code here) and that will give a new code $C_2$ with all the transversal gates conjugated by $U$. Although you are surely right that these are not "the same" gates and they do not generate "the same group" they do generate an isomorphic group, since conjugation is always an isomorphism. Oct 17, 2022 at 14:00