# Are two-qubit unitaries necessary for universal quantum computation?

I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said,

Two-qubit unitaries $U_t$ are necessary for universal quantum computation

I understand that there are universal sets of two-qubit quantum gates but does it imply that the set must always consist of two-bit gates?

-
How else would you get something like CNot? – Logan Mayfield Apr 24 '14 at 15:34

No, it is not necessary for a set of gates universal for quantum computation to contain a two-qubit gate.

A common example of a set of gates universal for quantum computation is $\{H, R_{\pi / 4}, \operatorname{CNOT}\}$, where $H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ is the (one-qubit) Hadamard gate, $R_{\pi / 4} = \begin{bmatrix} 1 & 0 \\ 0 & e^{\pi i / 4} \end{bmatrix}$ is the (one-qubit) $\frac{\pi}{8}$-gate, and $\operatorname{CNOT} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$ is the (two-qubit) controlled NOT gate. To obtain a set of gates universal for quantum computation but without any two-qubit gates, we can simply replace the two-qubit gate $\operatorname{CNOT}$ with the three-qubit gate $\operatorname{CNOT} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$. This three-qubit gate applies $\operatorname{CNOT}$ to the first two qubits and ignores the third qubit.

The correct statement is:

One-qubit unaries are not sufficient for universal quantum computation.

-
A much better example is Hadamard + Toffoli. While still in violation of the likely spirit of the question, it is a smaller violation than a gate basis whose sole multi-qubit operation is a two-qubit-and-also-a-one-qubit operation; and also the result is in itself interesting (that quantum computation is not "about" complex amplitudes per se, and can be simulated with bounded error by two such simple operations). – Niel de Beaudrap Apr 24 '14 at 22:43

I think this question is probably better suited to cs.stackexchange.com, and I hesitate to answer it. That single qubit gates are not universal was stated by Deutsch, Barenco, and Ekert in 1995. They point out that you cannot entangle un-entangled qubits with only single qubit operators. You can also prove this without any appeal to entanglement or states in general by showing that at least one two qubit operator, namely $CNot$, cannot be constructed by single qubit operators.

Assume single qubit operators are universal. Then there must exist some $A$ and $B$ such that $A \otimes B = CNot = (P_0 \otimes I) + (P_1 \otimes X)$. It follows then that that $A_{00}B = I$, $A_{11}B = X$, and $A_{01}B=A_{10}B=0$. For $A_{00}B$ to be $I$, it must be the case that $B$ itself is $I$. Similarly, for $A_{11}B$ to be $X$, $B$ itself must be $X$. This is a contradiction. So, single qubit operators are not universal as they cannot carry out at least one two qubit unitary operation, namely $CNot$.

-