# 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 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 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 & \mathbf{0}_2 \\ \mathbf{0}_2 & \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 & 1 \\ 1 & 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.