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