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?
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$.