# What are the transversal gates of Shor's [[9,1,3]] code?

What are the transversal gates of Shor's $$[[9,1,3]]$$ code?

Since this is a stabilizer code we have transversal Pauli gates. Indeed, transversal $$X^{\otimes 9}$$ implements logical $$\overline Z$$ and transversal $$Z^{\otimes 9}$$ implements logical $$\overline X$$. And since it is a CSS code then transversal $$CNOT$$ implements logical $$CNOT$$. See for example this question.

Are there any others?

I am primarily interested in other single qubit gates that are transversal for a single block of the code. But I would also be very curious to see any two qubit gates which are transversal for two blocks of the code (and higher for three blocks of the code etc...).

Side note: It is interesting to note that if one would rather have transversal $$X^{\otimes 9}$$ implement logical $$\overline X$$ and $$Z^{\otimes 9}$$ implement logical $$\overline Z$$ then one can take the image of $$[[9,1,3]]$$ code under $$H^{\otimes 9 }$$. For this new code, obtained by just swapping all the $$X$$s and $$Z$$s in the stabilizer, the logical states are just the old logical states but with every $$|0>$$ made into a $$|+>$$ and every $$|1>$$ made into a $$|->$$.

LONG DIGRESSION ABOUT TRANSVERSAILITY, A RESPONSE TO A COMMENT, NOT PART OF THE QUESTION :

There are a lot of of definitions of transversal gate floating around. But there are only two definitions that tend to be of interest to more mathematically inclined people. The first is a very strict equivariance condition where we say $$G^{\otimes n}$$ is transversal on an $$[[n,1,d]]$$ code if it implements logical $$G$$. The second, more widely used but often equivalent to the first in many examples of interest thus leading to a lot of confusion, is that a transversal gate is any gate of the form $$\otimes_{i=1}^n G_i$$ which implements any logical gate. For a stabilize code with stabilizer $$S$$ that is equivalent to saying that $$\otimes_{i=1}^n G_i$$ is in the normalizer of $$S$$. In other words, the transversal gates are the normalizer of $$S$$ in the group which is called $$\mathcal{T}:=\otimes_{i=1}^n U_2$$ " the group of unitary product operators" in the original paper of Eastin and Knill. Here $$U_2$$ is the $$2 \times 2$$ unitary group. Eastin-Knill call this normalizer $$\mathcal{G}:=N_{\mathcal{T}}(S)$$ "the group of logical product operators" again using notation and terminology of original Eastin-Knill. (here note that I have already specialized to stabilizer codes so I can write things in terms of $$S$$ and normalizers of $$S$$ etc... whereas Eastin-Knill work with generic codes so they cannot). Since elements of the normalizer which only differ by an element of the stabilizer have the same logical effect the note groups of transversal logical operators "logical product operators" is less redundantly thought of as $$N_{\mathcal{T}}(S)/S$$ here it is worth noting that the normalizer also includes all the global phase operators which we should really also mod out by since they do nothing.

Another annoying thing people do is say things like "transversal X" to mean $$X^{\otimes n}$$ without first establishing if this unitary product operator actually preserves the code space. For example I do that annoying thing several times in the second paragraph of my question above.

Anyway this is all to say that "transversal" at its broadest means "any physical gate which implements a logical gate and is naturally fault-tolerant". But that is very squishy definition. To most mathematically inclined people "transversal" means "any physical gate which implements a logical gate and is a unitary product operator (i.e. an element of $$\mathcal{T}$$). This is the sense in which I asked the question and in which Adam Zalcman answered. At its strictest, "transversal" means "a logical gate $$G$$ which can be implemented by acting one copy of $$G$$ on each physical qubit".

This very strict definition $$G \to G^{\otimes n}$$ is nice mathematically because it is just an equivariance condition for the encoding map. Also this is how we often see transversal gate come up in practice. Let $$CSS(C_1,C_2)$$ be as CSS code. For example transversal $$CNOT$$ on two blocks of any $$[[n,1,d]]$$ CSS code satisfies this strict equivariance condition. The same is true for a Hadamard gate on an $$[[n,1,d]]$$ CSS code with $$C_1=C_2$$ (this is sometimes call a self-dual CSS code although perhaps better to call this weakly self-dual). Since many of us get our intuition from $$X,Z,H,CNOT$$ on $$[[7,1,3]]$$ code, it is understandable to be confused about these two definitions of transversality.

Some well known example where they differ is transversal Paulis for Shor code and another good example is that transversal $$T$$ gate on $$[[15,1,3]]$$ implements logical $$T^\dagger$$ and transversal phase $$P$$ gate on $$[[7,1,3]]$$ implements logical $$P^\dagger$$.

Also note that most of what I've said here is for $$[[n,1,d]]$$ codes and thus transversality for single qubit gates. For transversal $$2$$ qubit gates like $$CNOT$$ on the Steane code one can think of 2 block as a $$[[14,2,3]]$$ code with $$CNOT^{\otimes 7}$$ implementing logical $$CNOT$$.

• No transversal $H$ or $CZ$ gates are possible. Also the code is not doubly even, so no $P$ gate either. There could be more "exotic" gates that would work but I didn't try to look. Jul 1 at 17:26

## Superpositions are too entangled

The logical computational basis of the Shor's nine-qubit code is

\begin{align} |0\rangle_L=\frac{((|000\rangle+|111\rangle)(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)}{\sqrt{8}}\\ |1\rangle_L=\frac{((|000\rangle-|111\rangle)(|000\rangle-|111\rangle)(|000\rangle-|111\rangle)}{\sqrt{8}}. \end{align}\tag1

The first three qubits in $$|0\rangle_L$$ and $$|1\rangle_L$$ are not entangled with the rest. However, in any logical superposition state $$\alpha|0\rangle_L+\beta|1\rangle_L$$ the first three qubits are entangled with the rest. Since entanglement cannot be created by transversal gates, we conclude that transversal gates cannot create superpositions of $$|0\rangle_L$$ and $$|1\rangle_L$$. Consequently, the single-qubit unitary effected on the code subspace by a transversal gate takes one of two forms

$$\overline A\equiv\begin{bmatrix}1&0\\0&e^{i\theta}\end{bmatrix}\quad \overline B\equiv\begin{bmatrix}0&1\\e^{i\theta}&0\end{bmatrix}\tag2$$

where $$\equiv$$ denotes equality up to global phase. Note that this encompasses all logical Pauli operators, $$\overline I$$, $$\overline X$$, $$\overline Y$$ and $$\overline Z$$, as expected. We need to take a closer look to more rigorously eliminate the possibility of transversal realization of gates outside the Pauli group.

## Useful commutation relation

Let's first write down a useful observation

Lemma If $$U\in SU(2)$$ commutes with $$Z$$ up to a constant, i.e.

$$UZU^\dagger=cZ\tag3$$

then either $$c=1$$ and $$U$$ is a $$Z$$ rotation or $$c=-1$$ and $$U\equiv n_xX+n_yY$$ for $$n_x,n_y\in\mathbb{R}$$ with $$n_x^2+n_y^2=1$$.

Proof Conjugation preserves eigenvalues, so $$c\in\{-1,+1\}$$. We can write $$U$$ as

$$U=\cos\frac{\theta}{2}I-i\sin\frac{\theta}{2}(n_xX+n_yY+n_zZ)\tag4$$

where $$\theta\in[0,4\pi)$$ and $$(n_x,n_y,n_z)$$ is a unit vector in $$\mathbb{R}^3$$. Substituting into the first equation in $$(3)$$ and carrying out the calculations we arrive at

\begin{align} \cos^2\frac{\theta}{2}+\sin^2\frac{\theta}{2}(n_z^2-n_x^2-n_y^2)=c. \end{align}\tag5

If $$c=+1$$ then $$n_z=1$$ and $$\theta$$ may be any angle, so $$U$$ is a $$Z$$ rotation. If $$c=-1$$ then $$\theta\in\{\pi,3\pi\}$$ and $$n_x^2+n_y^2=1$$, so $$U\equiv n_xX+n_yY$$ up to global phase.$$\square$$

## Single-qubit components form dihedral group

A popular choice of stabilizer generators for the Shor's nine-qubit code is

\begin{align} g_1&=ZZI,III,III\\ g_2&=IZZ,III,III\\ g_3&=III,ZZI,III\\ g_4&=III,IZZ,III\\ g_5&=III,III,ZZI\\ g_6&=III,III,IZZ\\ g_7&=XXX,XXX,III\\ g_8&=III,XXX,XXX \end{align}\tag6

where I have left tensor product signs implicit and inserted commas for readability. Since the stabilizer group $$\mathcal{S}$$ is abelian and all its elements square to identity, every stabilizer operator may be written as

$$g=g_1^{b_1}g_2^{b_2}\dots g_8^{b_8}\tag7$$

where $$b=b_1,b_2,\dots,b_8\in\mathbb{Z}_2^8$$ is any of the $$256$$ sequences of eight bits. Suppose $$\overline U=U_1U_2U_3,U_4U_5U_6,U_7U_8U_9$$ is a transversal gate. Then $$\overline{U}g_k\overline{U}^\dagger\in\mathcal{S}$$ for every $$k=1,\dots,8$$. Consider for concreteness $$g=\overline{U}g_1\overline{U}^\dagger$$. We have

$$g = (U_1ZU_1^\dagger)\otimes\dots\otimes(U_9IU_9^\dagger)=V_1V_2I,III,III\tag8$$

where $$V_1=U_1ZU_1^\dagger$$ and $$V_2=U_2ZU_2^\dagger$$ are Pauli operators. Notice that $$g$$ acts as identity on qubits seven through nine, so $$b_8=0$$. Also, it acts as identity on qubits four through six, so $$b_7=0$$ also. The same arguments apply to the $$Z$$ sector. In particular, since $$g$$ acts as identity on the ninth qubit, we have $$b_6=0$$. Since it acts as identity on the seventh qubit, we have $$b_5=0$$. Continuing, we have $$b_4=b_3=b_2=0$$. The only two remaining possibilities are $$b=0000,0000$$ and $$b=1000,0000$$. However, conjugation preserves eigenvalues, so $$b_1=1$$. Therefore, $$V_1=V_2=Z$$.

The same arguments apply to other $$Z$$-sector generators, so $$\overline{U}g_k\overline{U}^\dagger=g_k$$ for $$k=1,\dots,6$$. By similar arguments, we find that $$\overline{U}$$ maps the $$X$$-sector generator $$g_7$$ ($$g_8$$) to a product of $$Z$$-sector generators and $$g_7$$ ($$g_8$$) that consists solely of $$I$$, $$X$$ and $$Y$$ operators. For example, $$\overline{V}= ISS,ISS,ISS$$ where $$S=\mathrm{diag}(1, i)$$ fixes all $$Z$$-sector generators and maps $$g_7$$ to $$g_2g_4g_7=XYY,XYY,III$$. (Examining its action on $$(1)$$, we see that $$\overline{V}$$ is just another way to realize transversal $$\overline{X}$$.)

By tracing out eight qubits in $$\overline{U}g_k\overline{U}^\dagger=g_k$$ for $$k=1,\dots,6$$, we see that $$U_i$$ commutes with $$Z$$ up to a constant $$U_iZU_i^\dagger = cZ$$ for every $$i=1,\dots,9$$. Therefore, by the lemma above $$U_i=R_z(\theta)=\cos\frac{\theta}{2}+i\sin\frac{\theta}{2}Z$$ for some angle $$\theta$$ or $$U_i=n_xX+n_yY$$ for some $$n_x,n_y\in\mathbb{R}$$ such that $$n_x^2+n_y^2=1$$. Similarly, considering the action of $$\overline{U}$$ on the $$X$$-sector we see that $$U_iXU_i^\dagger = cX$$ or $$U_iXU_i^\dagger = cY$$. Calculation shows that for $$U_i$$ which is a $$Z$$ rotation this implies that $$\theta$$ is an integer multiple of $$\frac{\pi}{2}$$. Similarly, for $$U_i$$ of the form $$n_xX+n_yY$$ this implies that $$n_x=1$$ or $$n_y=1$$ or $$n_y=\pm\frac{1}{\sqrt{2}}$$. In other words, $$U_i\in\{I, S, Z, S^\dagger, X, Y, (X+Y)/\sqrt2, (X-Y)/\sqrt2\}$$. Ignoring the global phase $$(X+Y)/\sqrt2\equiv SX$$ and $$(X-Y)/\sqrt2\equiv XS$$, so $$U_i\in\langle S,X\rangle$$ where $$\langle S,X\rangle$$ is the dihedral group of order eight generated by $$S$$ and $$X$$.

## Exhaustive computer search

We have reduced the number of transversal operators that preserve the code subspace to no more than $$8^9\approx 134$$ million. This makes the problem of finding transversal realizations of logical single-qubit gates for the Shor's nine-qubit code amenable to exhaustive computer search.

0/0 transversal identity: I.I.I.I.I.I.I.I.I
1/11 transversal identity: I.I.I.I.I.I.I.S.SZ
2/18 transversal identity: I.I.I.I.I.I.I.Z.Z
3/25 transversal identity: I.I.I.I.I.I.I.SZ.S
4/67 transversal identity: I.I.I.I.I.I.S.I.SZ
5/74 transversal identity: I.I.I.I.I.I.S.S.Z
6/81 transversal identity: I.I.I.I.I.I.S.Z.S
7/88 transversal identity: I.I.I.I.I.I.S.SZ.I
8/130 transversal identity: I.I.I.I.I.I.Z.I.Z
9/137 transversal identity: I.I.I.I.I.I.Z.S.S
10/144 transversal identity: I.I.I.I.I.I.Z.Z.I
11/155 transversal identity: I.I.I.I.I.I.Z.SZ.SZ
12/193 transversal identity: I.I.I.I.I.I.SZ.I.S
13/200 transversal identity: I.I.I.I.I.I.SZ.S.I
14/211 transversal identity: I.I.I.I.I.I.SZ.Z.SZ
15/218 transversal identity: I.I.I.I.I.I.SZ.SZ.Z
16/292 transversal Z: I.I.I.I.I.I.X.X.X
17/301 transversal Z: I.I.I.I.I.I.X.Y.Y
18/311 transversal Z: I.I.I.I.I.I.X.SX.XS
19/318 transversal Z: I.I.I.I.I.I.X.XS.SX
20/357 transversal Z: I.I.I.I.I.I.Y.X.Y
21/364 transversal Z: I.I.I.I.I.I.Y.Y.X
22/374 transversal Z: I.I.I.I.I.I.Y.SX.SX
...
65518/133692115 transversal identity: XS.XS.Y.XS.XS.Y.SZ.Z.SZ
65519/133692122 transversal identity: XS.XS.Y.XS.XS.Y.SZ.SZ.Z
65520/133692196 transversal Z: XS.XS.Y.XS.XS.Y.X.X.X
65521/133692205 transversal Z: XS.XS.Y.XS.XS.Y.X.Y.Y
65522/133692215 transversal Z: XS.XS.Y.XS.XS.Y.X.SX.XS
65523/133692222 transversal Z: XS.XS.Y.XS.XS.Y.X.XS.SX
65524/133692261 transversal Z: XS.XS.Y.XS.XS.Y.Y.X.Y
65525/133692268 transversal Z: XS.XS.Y.XS.XS.Y.Y.Y.X
65526/133692278 transversal Z: XS.XS.Y.XS.XS.Y.Y.SX.SX
65527/133692287 transversal Z: XS.XS.Y.XS.XS.Y.Y.XS.XS
65528/133692327 transversal Z: XS.XS.Y.XS.XS.Y.SX.X.XS
65529/133692334 transversal Z: XS.XS.Y.XS.XS.Y.SX.Y.SX
65530/133692341 transversal Z: XS.XS.Y.XS.XS.Y.SX.SX.Y
65531/133692348 transversal Z: XS.XS.Y.XS.XS.Y.SX.XS.X
65532/133692390 transversal Z: XS.XS.Y.XS.XS.Y.XS.X.SX
65533/133692399 transversal Z: XS.XS.Y.XS.XS.Y.XS.Y.XS
65534/133692404 transversal Z: XS.XS.Y.XS.XS.Y.XS.SX.X
65535/133692413 transversal Z: XS.XS.Y.XS.XS.Y.XS.XS.Y

Found the following number of transversal realizations of logical operators:
identity: 16384
X: 16384
Y: 16384
Z: 16384
other: 0

real    31m30.748s
user    31m30.290s
sys     0m0.157s


We conclude that Pauli operators $$\overline I$$, $$\overline X$$, $$\overline Y$$ and $$\overline Z$$ are the only single-qubit logical gates with transversal realizations.

• Why is $\bar U=U_1 U_2 U_3,U_4 U_5 U_6,U_7 U_8 U_9$? shouldn't the same gate be applied to every qubit? so $U_1=U_2=U_3,\cdots$; Jul 3 at 15:03
• @unknown There are a lot of of definitions of transversal gate floating around. But there are only two definitions that tend to be of interest to more mathematically inclined people. The first is a very strict equivariance condition where we say $G^{\otimes n}$ is transversal on an $[[n,1,d]]$ code if it implements logical $G$. The second, more widely used but often equivalent to the first in many examples of interest thus leading to a lot of confusion, is that a transversal gate is any gate of the form $\otimes_{i=1}^n G_i$ which implements any logical gate. I'll edit to add details Jul 3 at 18:29
• it makes a huge difference in the search space $8$ vs $8^9$. Jul 3 at 18:59
• +1 to what Ian said. The first definition ($G^{\otimes n}$) is certainly easier to analyze. The second definition better captures the intent, though. Namely, the transversal construction is meant to be a very simple and fault-tolerant implementation of a logical gate. Here, "fault-tolerance" means that the gate does not multiply errors. More precisely, it means that if the input block has $k$ errors initially and no errors occur during the gate then the block should have at most $k$ errors after the gate. This condition is satisfied by any gate of the form $U_1\otimes\dots\otimes U_n$. Jul 3 at 20:01
• @unknown Even-distance surface code would be one example. Another can be constructed from the above answer by replacing three groups of three qubits with four groups of four qubits. Jul 4 at 3:44

The code is not symmetric in $$X$$ and $$Z$$ type stabilizers $$|S_X|=6$$ and $$|S_Z|=2$$; so $$H_L=H^{\otimes 9}$$ doesn't preserve the codespace and you can't have a transversal $$H_L$$.

$$U=H P$$ is transversal where $$P=((1,0),(0,\imath))$$;

$$U^\dagger Z U=\imath Z X$$; $$U^\dagger X U=Z$$;

$$U X U^\dagger=\imath X Z$$; $$U Z U^\dagger=X$$;

$$U^{\otimes 9} : Z_L \to X_L, X_L \to \imath^9 X_L Z_L$$ which is $$U_L^\dagger$$.

Correction to answer : even though $$U=HP$$ has the right action on the logicals, it doesn't preserve the codespace so it's not transversal.

• First of all thank you for your excellent answer to some of my other questions for example:quantumcomputing.stackexchange.com/questions/26701/… and quantumcomputing.stackexchange.com/questions/27134/…. You are an intelligent and generous person. Second of all, your claim that $HP$ is transversal is wrong. Here is my reasoning: Conjugation by $HP$ does not preserve that code space because it does not preserve the stabilizer. Jul 3 at 1:17
• Indeed acting by conjugation on, for example, $ZZIIIIIII$ yields $XXIIIIIII$ which is clearly not in the stabilizer since it does not commute with $IZZIIIIII$. Your argument about preserving logical Paulis $X_L$ and $Z_L$ is not valid because there are many representatives of the logical Paulis ( the logical Pauli group for stabilizer code with stabilizer $S$ is given by $N(S)/S$). Some choices of logical Pauli are transformed under conjugation as you say, such as $XXXXXXXXX$ and $ZZZZZZZZZ$, but other logical operators like $ZIIZIIZII$, which is a logical $X_L$ Jul 3 at 1:33
• you're right...I totally missed that even though it's obvious...(and you're being very generous...I'm just learning like everyone else) Jul 3 at 1:35
• transform to something which is not even in the stabilizer. And no problem this kind of stuff happens to everyone! Jul 3 at 1:36