# Quantum gates

A unitary operator on a qubit is usually called a (quantum) gate and acts on the basis

$|0\rangle = \begin{pmatrix}1 \\0\end{pmatrix}\;|1\rangle = \begin{pmatrix}0\\1\end{pmatrix}.$

The NOT gate $N$ is defined as

$N\,|0\rangle = |1\rangle,\; N\,|1\rangle = |0\rangle$

and has matrix representation

$N = \begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}$.

The $N = \begin{pmatrix}0 & 1\\ 1 & 0\end{pmatrix}$. operation $\oplus$ corresponds to a $\mathbb{Z}_2$ addition and hence

$N\,|x\rangle = |x\oplus 1\rangle$.

The identity gate $\mathbb{1}$ is

$\mathbb{1} = \begin{pmatrix}1 & 0\\ 0 & 1\end{pmatrix}$

$H =\frac{1}{\sqrt{2}} \begin{pmatrix}1 & 1\\ 1 & -1\end{pmatrix}$.
The CNOT operator and acts on two qubits as follows

$CNOT\,|00\rangle = |00\rangle,\;CNOT\,|01\rangle = |01\rangle,\\CNOT\,|10\rangle = |11\rangle,\;CNOT\,|11\rangle = |10\rangle$

meaning that the second qubit is flipped if the first one is 1. The matrix representation is

$CNOT = \begin{pmatrix}1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{pmatrix}$.

A state which cannot be written as a direct product of two states is called entangled and it means that the state should be considered as one. It effectively means that in reality such a system acts as one despite long distances and does not obbey special relativity. This does not break any fundamental theory because there is no information exchange. A two qubit system has four entangled states called ebits:

$\frac{1}{\sqrt{2}}(\,|00\rangle+|11\rangle\,),\\\frac{1}{\sqrt{2}}(\,|00\rangle-|11\rangle\,),\\\frac{1}{\sqrt{2}}(\,|01\rangle+|10\rangle\,),\\\frac{1}{\sqrt{2}}(\,|01\rangle-|10\rangle\,).$

The Toffoli gate (also known as the CCNOT gate) acts on three qubits and maps $a, b, c$ to $c\oplus ab$ with matrix representation

$CCNOT = \begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\end{pmatrix}$.

It can be shown that the Toffoli gate is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates.