CNOT

The CNOT gate is one of the most important \; 2-qubit gates and is represented in the standard basis \; \{|0\rangle, |1\rangle\} by the following \; 4 \times 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 \; \mathbf{1}_2 , \mathbf{0}_2 are the \; 2 \times 2 identity and null matrices respectively and \; \sigma_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 \; U_{CNOT} on two qubits operationally. We take two qubits \; |x\rangle and \; |y\rangle, 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\rangle \otimes |y\rangle] = |x\rangle \otimes |x \oplus y\rangle ,

where \; x \oplus 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 n) such gates.

Retrieved from "http://www.quantiki.org/wiki/index.php/CNOT"