How to intuitively understand why $T$ gate can't be implemented transversally?

Suppose we have all to all connectivity and can implement fault-tolerant logical gates in the Clifford group. Why can't we just apply a physical $$T$$ gate to every physical qubit in the code block? (Suppose we have stabilizer generators like a bunch of Xs and a bunch of Zs.)

Similarly, since CNOT can be applied transversally, why can't a CCX be applied transversally and maintain fault tolerance?

TL;DR: It is not true that $$T$$ gate can't be implemented transversally. However, universal gatesets, such as $$\text{Clifford}{+}T$$, cannot be implemented transversally by Eastin-Knill theorem. The reason for this is that the set of transversal gates is a finite group. A finite group - unlike a finite set - cannot approximate an infinite set of all unitaries arbitrarily well.

Background

Transversality is not a property of a gate alone. It is a relationship between a gate and a quantum error correcting code. Moreover, it is not true that the $$T$$ gate cannot be implemented transversally. In fact, the existence of quantum codes that admit transversal $$T$$ gate underlies magic state distillation. An example of a large family of such codes is provided by the triorthogonal CSS codes, see here, here and here.

However, it is true that no quantum error correcting code capable of detecting all local errors admits a universal set of transversal gates. This result is known as the Eastin-Knill theorem. Note that this does not contradict the existence of codes with transversal $$T$$ gate since $$T$$ gate is not universal. In fact, even gatesets such as $$\text{CNOT}{+}T$$ or $$\text{Toffoli}{+}T$$ fail to be universal since they cannot create superpositions of computational basis states.

Now, $$\text{Clifford}{+}T$$ is a universal set of gates, so if a given code admits transversal$$^1$$ Cliffords, then it cannot admit transversal $$T$$ gate. Thus, in order to provide an intuitive answer to the question why such codes cannot admit transversal $$T$$ gate one needs to explain why $$\text{Clifford}{+}T$$ is a universal set of gates and why a universal set of gates cannot be transversal.

Why is $$\text{Clifford}{+}T$$ universal?

In short, the universality of the $$\text{Clifford}{+}T$$ gateset follows from two constructions, one exact and one approximate. First, it turns out that an arbitrary $$n$$-qubit unitary may be expressed as the product of the so-called two-level unitaries, i.e. unitaries that act non-trivially on a two-dimensional subspace only. Moreover, it is possible to construct a quantum circuit implementing any two-level unitary using CNOT and arbitrary single-qubit gates.

Second, it turns out that $$\text{Clifford}{+}T$$ contains enough single-qubit gates to approximate any single-qubit gate arbitrarily well. In a little more detail, the approximation is achieved by using two $$\frac{\pi}{4}$$ rotations: one around the $$Z$$ axis provided by the $$T$$ gate and one around the $$X$$ axis constructed as $$HTH$$. It turns out that their composition is a rotation by an angle which is an irrational multiple of $$\pi$$. The significance of irrationality here lies in the fact that repeated application of the resulting gate densely fills the unit circle. This can be done around two different axes which is sufficient to approximate any single-qubit gate arbitrarily well. See here for the proof and VII F 2 in here for the application of the techniques in that proof to the gateset of Google's Sycamore processor.

Why can't a transversal gateset be universal?

Composing two transversal logical operators yields a transversal logical operator. Identity is a transversal logical operator and the inverse of a transversal logical operator is a transversal logical operator.

In other words, transversal logical operators form a group. In fact, it is a Lie subgroup of the Lie group of all unitaries on the code block. A Lie group is also a topological manifold and consists of a number of connected components. One of these components contains the identity. Using the properties of the associated Lie algebra, it can be shown that for a code capable of detecting all local errors all operators in the connected component containing identity act trivially on the code subspace. This means that the number of distinct transversal logical operators is at most the number of connected components of the group. However, the group is compact, so the number is finite. See here for more details.

Thus, the number of transversal logical operators in any quantum code capable of detecting all local errors is finite. However, no finite group can approximate an infinite set of operators arbitrarily well.

Note the significance of the fact that transversal logical operators form a group. By Solovay-Kitaev theorem, a finite set of operators can be used to approximate an infinite set of operators arbitrarily well. In fact, $$\text{Clifford}{+}T$$ is one example of such set. However, the set cannot be closed under composition. Thus, in a sense, the combination of finite size and closure under composition prevents every set of transversal logical operators from being universal.

$$^1$$ Note that the transversal construction isn't the only way to realize fault-tolerant logical gates. If a code implements fault-tolerant Cliffords using constructions other than transversality, then a transversal $$T$$ gate is not necessarily ruled out. This is why the tension between fault-tolerance and universality expressed in the Eastin-Knill theorem does not dissuade people from working to build quantum computers.

Suppose you have a code where the logical Z observable is all of the qubits. Then, for the T gate to be transversal, you basically need this to be true:

$$\sqrt{\sqrt{\prod_{q} Z_q}} = \prod_{q} \sqrt{\sqrt{Z_q}}$$

And why would you expect that to be true? Expecting the above to work is like expecting $$1 = \sqrt{-1 \cdot -1} = \sqrt{-1} \sqrt{-1} = -1$$ to work. You need to go out of your way to avoid introducing mistakes when doing stuff like that.

As a specific example, consider the two qubit repetition code which has a single stabilizer $$X_1X_2$$, a logical X of $$X_1$$, and a logical Z of $$Z_1 Z_2$$. Note that $$T_L = \sqrt{\sqrt{Z_1 Z_2}}$$ commutes with the stabilizer $$X_1 X_2$$, as any logical operation must, but $$T_1 T_2 = \sqrt{\sqrt{Z_1}} \sqrt{\sqrt{Z_2}}$$ doesn't commute with the stabilizer. Therefore it's not a logical operation, nevermind specifically being the logical T. You can confirm that it anticommutes by simply computing the commutator.

• I think I understand what you're trying to say, but mathematically this isn't right. In particular, the paradoxical "derivation" suggests that the reason the first equation can't be satisfied has something to do with the multi-valued nature of the complex $n$th root. In reality, the $T$ gate is not defined in terms of roots at all. Instead, it is defined as e.g. $T=\mathrm{diag}(1,e^{i\pi/4})$ which is free of ambiguity or multi-valued-ness. Commented Sep 5, 2022 at 4:08
• If I understand your intention correctly, the first equation should read something like $$\cos\frac{\pi}{8}I^{\otimes n}-i\sin\frac{\pi}{8}Z^{\otimes n}=\left(\cos\frac{\pi}{8}I-i\sin\frac{\pi}{8}Z\right)^{\otimes n}$$ where it makes sense to ask why one should expect it to be true. After all, after carrying out the tensor product RHS ends up with a lot more terms than LHS and all those extra terms need to cancel out in order for the equation to hold. It is possible to engineer the terms to cancel out (as in triorthogonal codes) but IIUC your point is that generally speaking they won't. Commented Sep 5, 2022 at 4:10
• There is another important point about the first equation: we only need something like it to be true on the code subspace. Commented Sep 5, 2022 at 4:11
• @AdamZalcman the principle root ambiguity really is the underlying issue, in my view. The square root operates on the eigenvalues of the matrix. Doing roots first turns every -1 eigenvalue into ✓i. Doing roots second, some of those -1s combined info +1 and root into +1 instead. They produce different operations, but only one operation is the intended one. Commented Sep 5, 2022 at 11:21
• More generally, my answer is only intended to convey the intuition of why this wouldn't just magically work, because the asker clearly had the opposite intuition. That's also why I gave such a simple example. Commented Sep 5, 2022 at 11:27