# Non-universal gate sets

Imagine that I have the gate $$T=\text{diag}(1,e^{i\pi/4})$$ and want to add to it some two-qubit gate $$U$$ such that the set $$\{U,T\}$$ is not universal for quantum computation. What limits are there on the choice of $$U$$?

I already know that $$U$$ could be any permutation matrix with phases. For example, the controlled-not gate or any diagonal gate. But are there any other cases? I guess (but would love to have a reference for where this is proven) that as soon as $$U$$ has an element $$U_{ij}$$ such that $$|U_{ij}|\neq 0,1$$, then $$T+U$$ is universal.

• If $U$ created any superposition then could you use $T$ and $U$ (with one input fixed to say $|0\rangle$) to simulate an $H$? Commented Jun 1, 2022 at 12:10
• @MarkS That is certainly the intuition, but can it always be done? Commented Jun 1, 2022 at 13:14
• I think some clarification on the "rules" are needed. 1) Do I get to use measurement and (classically) conditional versions of these gates? 2) What about encoded universality, where one gets universality but only on a subsystem or subspace? Commented Jun 9, 2022 at 22:22
• @dabacon No measurement. When I ask for "non-universal", I include within that "should not have encoded universality". (Some of the context for the question comes from trying to establish the existence of sets of transversal gates, so I know that the gate set should not be universal by Eastin-Knill, including encoded, or even just encoded single-qubit universality, which eliminates all the options in the answers so far, but that's not strictly what I asked...) Commented Jun 10, 2022 at 6:56

Yes, there are other cases.

## Superposition and entanglement

The proposed rule

$$\text{if U has an element U_{ij} such that |U_{ij}|\notin\{0,1\}},\\ \text{then the set \{T,U\} is universal}\tag1$$

appears motivated by the observation that any set of permutation gates with phases fails to create superposition states when acting on a computational basis state. However, the rule $$(1)$$ doesn't work, because the ability to create superpositions is necessary but not sufficient for universality. For example, any product unitary such as

$$H\otimes H=\frac12\begin{bmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{bmatrix}\tag2$$

fails to create entanglement so $$\{T, H\otimes H\}$$ fails to be universal.

## Stuck in a subspace

In fact, the ability to create superpositions and entanglement is still not sufficient. A gateset may fail to be universal by failing to act transitively on quantum states. For example, if $$V=\begin{bmatrix}a&b\\c&d\end{bmatrix}\in U(2)$$, then $$\{T,U\}$$ with

$$U=\begin{bmatrix} 1&&&\\ &a&b&\\ &c&d&\\ &&&1 \end{bmatrix}\tag3$$

is not universal even though $$U$$ may create entangled states. This follows from the observation that all circuits consisting of $$T$$ and $$U$$ preserve$$^1$$ the number of $$0$$s and $$1$$s of an input state in the computational basis. In particular, any such circuit maps $$|0\dots 0\rangle$$ to itself.

$$^1$$ Gates of the form $$(2)$$ are sometimes called "excitation-preserving", because they map each state with $$k=0,1,2$$ qubits in the $$1$$ state to a state where $$k$$ qubits are in the $$1$$ state.
• I should have thought of both of those cases! Do you have a sense of whether those are the only other classes of case? Commented Jun 3, 2022 at 6:32
• There are still more cases, e.g. $\{T,V\}$ with $$V=\begin{bmatrix}w&&&x\\&1&&\\&&1&\\y&&&z\end{bmatrix}$$ is not universal because it preserves the number of $1$s modulo $2$. For the same reason $\{T,UV\}$ also fails to be universal. Admittedly, these are all fairly similar. Commented Jun 3, 2022 at 7:13
• FWIW, the analogue of rule $(1)$ does appear to work for the less general problem of $SU(2)$-universality of a gateset with $T$ and one more single-qubit gate. In this case there are some interesting non-universal gatesets such as $\{T,X\}$ which generates the dihedral group $D_4$, but it seems that as soon as one of the gates creates superpositions we can use the two gates to approximate any single-qubit unitary arbitrarily well. Commented Jun 3, 2022 at 7:17
• The second case, however, can lead to encoded universality. For example a single U with a partial exhange interaction will be universal by itself (see arxiv.org/abs/quant-ph/9909058 for example) Commented Jun 9, 2022 at 22:24