Universal Gate Set, Magic States, and costliness of the T gate

Question

The usual universal gate set is $\mathcal{C} + T$ where $\mathcal{C}$ is the Clifford group and $T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi/4} \end{pmatrix} $ is the $\pi/8$ rotation gate. In practice we find a code that has $\mathcal{C}$ transversal and then we use magic state distillation to "simulate" the $T$ gate.

However, we could have just as easily used the universal gate set $\mathcal{C} + M$ where $M$ is any matrix outside of the Clifford group. For example, the $T$ gate above is in the 3rd level of the Clifford hierarchy, but we could instead choose $M$ in the $4$th level (or even outside of the hierarchy).

There must be some reason people mainly use $T$? I have heard it said that "implementing $T$ is extremely costly" but "even higher levels of the hierarchy are worse." Can someone maybe explain this to me?

Note: On the other hand consider a 1-qubit universal gate set $\langle X, Z, T\rangle + H$ and find a code with transversal $X$, $Z$, and $T$ (like the $[[15,1,3]]$ Reed Muller code) whereby we simulate $H$ using magic states. Since $H$ is in the Clifford group wouldn't this offer up even more cost reduction?

Answer 1

The T state $Z^{1/4}|+\rangle$ has four core advantages over most other states:

1. You can physically inject T states at pretty high fidelity.
2. It has a reasonably cheap distillation circuit, as far as the sizes of these circuits typically go.
3. Four T states gives you a Toffoli. The Toffoli gate is an absolutely essential tool for building big classical operations like multipliers and multiplexers, so you need a lot of them.
4. When correcting gate teleportation involving T states, the correction is Clifford (i.e. cheap instead of requiring yet more magic states).

In my mind, the main competition to the T gate is the Toffoli state $\sum_{a,b\in \{0,1\}} |a,b,ab\rangle$ or equivalently the CCZ state $\text{CCZ}|+++\rangle = \sum_{a,b,c \in \{0,1\}} |a,b,c\rangle^{-abc}$. This is because you can consume one of those states in order to perform a Toffoli gate, instead of four. The downside of working directly with Toffoli states is that they are harder to inject and distill. That said, one very efficient thing you can do is to replace the last stage of 15T -> 1T state distillation with an 8T -> TOF distillation.

The next closest competitor is the CS state $\text{CS}|++\rangle$. You can do a Toffoli gate with two CS states. So the three main competitors are a two-control 180 degree rotation, a one-control 90 degree rotation, and a no-control 45 degree rotation. Too bad there's no three-control 360 degree rotation or minus-one-control 22.5 degree rotation.

Answer 2

Imagine you're interested in implementing a gate $$ P_k=\left(\begin{array}{cc} 1 & 0 \\ 0 & e^{i\pi/2^k} \end{array}\right), $$ so $Z=P_0$, $S=P_1$ and $T=P_2$. Now imagine that you're going through a process of distillation that involves a measurement somewhere. You get two possible outcomes. One is the gate that you want, $P_k$. Great! So, you've had $$ |\psi\rangle\longrightarrow P_k|\psi\rangle. $$ What happens if you get the other measurement result? Of course that depends on the precise details of the protocol, but you typically find that you introduce an $X$ error, $$ |\psi\rangle\longrightarrow P_kX|\psi\rangle. $$ We need to correct for this error. A good start would be to apply another $X$ $$ P_kX\longrightarrow XP_kX=P_k^\dagger=P_{k-1}^\dagger P_k. $$ Thus, to finish the correction, we should apply $P_{k-1}$.

This argument is intended to show you the heirarchy: if I try to implement $P_3$, I anyway need to be able to implement $P_2$ to make the correction. So, it would be much easier to just stick with making $P_2$.

---

To answer your question about the 15-qubit code, this is certainly another route to go. It is not clear whether you get a benefit because there's a trade-off: simpler gate implementations, but more qubits in your logical state. This is one reason why I got interested in making sure the 15-qubit code was the smallest one with transversal T. Then, how should one assess what code is better? Probably calculate a fault-tolerant threshold. But the main cost there is probably the controlled-not gate (becuase it involves twice as many qubits), and so the precise details of the single qubit gates possibly matter a bit less.

Answer 3

To shorten Craig's answer, T is a single qubit gate, diagonal in the Z basis, and still a relatively simple, easy-to-understand rotation. H for example is not a rotation.

For your last question - the set of codes with transversal T is pretty limited (see Codes which can perform non-Clifford gate fault-tolerantly for example), and each of them has its difficulties.