6

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.

Adam Zalcman
  • 22,278
  • 3
  • 34
  • 83
DaftWullie
  • 57,689
  • 3
  • 46
  • 124
  • If $U$ created any superposition then could you use $T$ and $U$ (with one input fixed to say $|0\rangle$) to simulate an $H$? – Mark Spinelli Jun 01 '22 at 12:10
  • @MarkS That is certainly the intuition, but can it always be done? – DaftWullie Jun 01 '22 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? – dabacon Jun 09 '22 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...) – DaftWullie Jun 10 '22 at 06:56

1 Answers1

5

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.
Adam Zalcman
  • 22,278
  • 3
  • 34
  • 83
  • I should have thought of both of those cases! Do you have a sense of whether those are the only other classes of case? – DaftWullie Jun 03 '22 at 06: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. – Adam Zalcman Jun 03 '22 at 07: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. – Adam Zalcman Jun 03 '22 at 07:17
  • 1
    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 https://arxiv.org/abs/quant-ph/9909058 for example) – dabacon Jun 09 '22 at 22:24