# CNOT

The CNOT gate is one of the most important  2-qubit gates and is represented in the standard basis  {∣0⟩, ∣1⟩} by the following  4 × 4 matrix:

$$\operatorname{U_{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}$$
.

The operator UCNOT is Hermitian and unitary, and can be rewritten as a block matrix in the form:

$$\operatorname{U_{CNOT}} = \begin{bmatrix} \mathbf{1}_2 &amp; \mathbf{0}_2 \\ \mathbf{0}_2 &amp; \sigma_1 \end{bmatrix}$$
, where 12, 02 are the  2 × 2 identity and null matrices respectively and σ1 is the Pauli matrix

$$\operatorname{\sigma_1} = \operatorname{\sigma_x} = \begin{bmatrix} 0 &amp; 1 \\ 1 &amp; 0 \end{bmatrix}$$
.

We can also rewrite the action of UCNOT on two qubits operationally. We take two qubits  ∣x and  ∣y, where the former is the so-called control qubit and the latter is the target qubit; then the action of UCNOT on the system of the two qubits is:

UCNOT[∣x⟩ ⊗ ∣y⟩] = ∣x⟩ ⊗ ∣x ⊕ y⟩,
where x ⊕ y = (x + y)mod 2.

The CNOT together with the Hadamard gate and all phase gates form an infinite universal set of gates, i.e. if the CNOT gate as well as the Hadamard and all phase gates are available then any n-qubit unitary operation can be simulated exactly with O(4nn) such gates.