6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ If $U$ created any superposition then could you use $T$ and $U$ (with one input fixed to say $|0\rangle$) to simulate an $H$? $\endgroup$
    – Mark Spinelli
    Jun 1, 2022 at 12:10
  • $\begingroup$ @MarkS That is certainly the intuition, but can it always be done? $\endgroup$
    – DaftWullie
    Jun 1, 2022 at 13:14
  • $\begingroup$ 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? $\endgroup$
    – dabacon
    Jun 9, 2022 at 22:22
  • $\begingroup$ @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...) $\endgroup$
    – DaftWullie
    Jun 10, 2022 at 6:56

1 Answer 1

Reset to default
5
$\begingroup$

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.
Improve this answer
$\endgroup$
4
  • $\begingroup$ I should have thought of both of those cases! Do you have a sense of whether those are the only other classes of case? $\endgroup$
    – DaftWullie
    Jun 3, 2022 at 6:32
  • $\begingroup$ 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. $\endgroup$
    – Adam Zalcman
    Jun 3, 2022 at 7:13
  • $\begingroup$ 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. $\endgroup$
    – Adam Zalcman
    Jun 3, 2022 at 7:17
  • 1
    $\begingroup$ 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) $\endgroup$
    – dabacon
    Jun 9, 2022 at 22:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.