Quantum Topology/CCNOT Gate

Definition¹

(From the definition of the classical Toffoli gate $(a, b, c) \mapsto (a, b, (a \land b) \oplus c)$) The quantum Toffoli gate for qubits $\ket{a, b, c} = \ket{a} \otimes \ket{b} \otimes \ket{c}$ is defined as follows.

$$ \begin{align*} T_{q} : (\mathbb{C}^{2})^{\otimes 3} &\to (\mathbb{C}^{2})^{\otimes 3} \\ \ket{a, b, c} &\mapsto \ket{a, b, (a \land b) \oplus c},\quad \forall a,b,c \in \left\{ 0, 1 \right\} \end{align*} $$

$$ \operatorname{CNOT}_{q} (\ket{a} \otimes \ket{b} \otimes \ket{c}) = \ket{a} \otimes \ket{b} \otimes \ket{ (a \land b) \oplus c } $$

Here $(\mathbb{C}^{2})^{\otimes 3}$ is the tensor product of vector spaces, $\ket{a} \otimes \ket{b} \otimes \ket{c}$ is the product vector, $\land$ is the logical AND, and $\oplus$ is the exclusive OR (XOR).

Description

It is the quantum computer version of the classical Toffoli gate. Whereas the classical Toffoli gate is a universal gate, the quantum Toffoli gate is not a universal gate. Not only the quantum Toffoli gate, but also there are no universal gates in quantum computing.

The specific input and output of $T_{q}$ are as follows. The output changes only when the input is $\ket{110}, \ket{111}$.

$$ T_{q} (\ket{000}) = \ket{0, 0, (0 \land 0) \oplus 0} = \ket{000} \\[0.5em] T_{q} (\ket{001}) = \ket{0, 0, (0 \land 0) \oplus 1} = \ket{001} \\[0.5em] T_{q} (\ket{010}) = \ket{0, 1, (0 \land 1) \oplus 0} = \ket{010} \\[0.5em] T_{q} (\ket{011}) = \ket{0, 1, (0 \land 1) \oplus 1} = \ket{011} \\[0.5em] T_{q} (\ket{100}) = \ket{1, 0, (1 \land 0) \oplus 0} = \ket{100} \\[0.5em] T_{q} (\ket{101}) = \ket{1, 0, (1 \land 0) \oplus 1} = \ket{101} \\[0.5em] T_{q} (\ket{110}) = \ket{1, 1, (1 \land 1) \oplus 0} = \ket{111} \\[0.5em] T_{q} (\ket{111}) = \ket{1, 1, (1 \land 1) \oplus 1} = \ket{110} \\[0.5em] $$

The matrix representation is as follows.

$$ T_{q} = \begin{bmatrix} 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{bmatrix} $$