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  U_CNOT 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  1₂, 0₂ are the  2 × 2 identity and null matrices respectively and  σ₁ 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  U_CNOT 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  U_CNOT on the system of the two qubits is:

 U_CNOT[∣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(4ⁿn) such gates.

Category:Evolutions and Operations Category:Models of Quantum Computation