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

<p>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 &amp; 1 \\ 1 &amp; -1 \end{bmatrix}$ is the (one-qubit) Hadamard gate, $R_{\pi / 4} = \begin{bmatrix} 1 &amp; 0 \\ 0 &amp; e^{\pi i / 4} \end{bmatrix}$ is the (one-qubit) $\frac{\pi}{8}$-gate, and $\operatorname{CNOT} = \begin{bmatrix} 1 &amp; 0 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 &amp; 0 \\ 0 &amp; 0 &amp; 0 &amp; 1 \\ 0 &amp; 0 &amp; 1 &amp; 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 &amp; 0 \\ 0 &amp; 1 \end{bmatrix}$.  This three-qubit gate applies $\operatorname{CNOT}$ to the first two qubits and ignores the third qubit.</p>

<p>The correct statement is:</p>

<blockquote>
  <p>One-qubit unaries are not sufficient for universal quantum computation.</p>
</blockquote>

CC BY-SA 3.0
2014-04-24T22:43:56.590Z
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
CC BY-SA 3.0
2014-04-24T22:12:32.817Z
2014-04-24T22:12:32.817Z
Tyson Williams
<p>I think this question is probably better suited to <a href="https://cs.stackexchange.com/">cs.stackexchange.com</a>, and I hesitate to answer it. That single qubit gates are not universal was stated by <a href="http://arxiv.org/abs/quant-ph/9505018" rel="nofollow noreferrer">Deutsch, Barenco, and Ekert</a> 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.</p>

<p>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$. </p>

CC BY-SA 3.0
2014-04-24T18:23:00.957Z
2014-04-24T18:56:32.470Z
2017-04-13T12:48:30.830Z
Logan Mayfield
<p>I was going through <a href="http://arxiv.org/abs/0908.4219" rel="nofollow">Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians</a> by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said,</p>

<blockquote>
  <p>Two-qubit unitaries $U_t$ are necessary for universal quantum
  computation</p>
</blockquote>

<p>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? </p>

CC BY-SA 3.0
2014-04-24T15:34:12.907Z
How else would you get something like CNot?
Logan Mayfield
<quantum-computing><quantum-information><universal-computation>
Are two-qubit unitaries necessary for universal quantum computation?
Omar Shehab
# Are two-qubit unitaries necessary for universal quantum computation?

(Asked by: username_0 on 2014-04-24)

I was going through [Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians](http://arxiv.org/abs/0908.4219) 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?

**Tags:** quantum-computing, quantum-information, universal-computation

> **Comments:**
> **username_1**: How else would you get something like CNot?  

---

## 2 answers

### Answer by username_2 on 2014-04-24. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_3**: 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).  

---

### Answer by username_1 on 2014-04-24. Score: 5

I think this question is probably better suited to [cs.stackexchange.com](https://cs.stackexchange.com/), and I hesitate to answer it. That single qubit gates are not universal was stated by [Deutsch, Barenco, and Ekert](http://arxiv.org/abs/quant-ph/9505018) 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$.


---

