Toffoli/CCNOT Gate

Definition¹

The following vector-valued Boolean function is called a Toffoli gate.

$$T : \left\{ 0, 1 \right\}^{3} \to \left\{ 0, 1 \right\}^{3}$$

$$T (a, b, c) = (a, b, (a \land b) \oplus c)$$

• The $\text{CCNOT}$ gate is also known as.

Description

In the Toffoli gate, if the first two inputs are both $1$, the third input is inverted. In all other cases, the input and output are the same. The specific calculation is as follows.

$$\begin{align*} T (0,0,0) &= (0, 0, (0 \land 0) \oplus 0) = (0, 0, 0 \oplus 0) = (0, 0, 0) \\ T (0,0,1) &= (0, 0, (0 \land 0) \oplus 1) = (0, 0, 0 \oplus 1) = (0, 0, 1) \\ T (0,1,0) &= (0, 1, (0 \land 1) \oplus 0) = (0, 1, 0 \oplus 0) = (0, 1, 0) \\ T (0,1,1) &= (0, 1, (0 \land 1) \oplus 1) = (0, 1, 0 \oplus 1) = (0, 1, 1) \\ T (1,0,0) &= (1, 0, (1 \land 0) \oplus 0) = (1, 0, 0 \oplus 0) = (1, 0, 0) \\ T (1,0,1) &= (1, 0, (1 \land 0) \oplus 1) = (1, 0, 0 \oplus 1) = (1, 0, 1) \\ T (1,1,0) &= (1, 1, (1 \land 1) \oplus 0) = (1, 1, 1 \oplus 0) = (1, 1, 1) \\ T (1,1,1) &= (1, 1, (1 \land 1) \oplus 1) = (1, 1, 1 \oplus 1) = (1, 1, 0) \\ \end{align*}$$

From the table above, it’s easy to see that $T$ is a reversible function and that applying $T$ twice composes to an identity function.

$$\operatorname{Id} = T \circ T$$

Furthermore, since $\left\{ T \right\}$ is functionally complete, $T$ is a universal gate.

부울 함수	기호	진리표
$T$		입력 출력 $a$ $b$ $c$ $a$ $b$ $(a \land b) \oplus c$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $1$ $0$ $1$ $0$ $0$ $1$ $0$ $0$ $1$ $1$ $0$ $1$ $1$ $1$ $0$ $0$ $1$ $0$ $0$ $1$ $0$ $1$ $1$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $0$

Theorem

(Assuming unrestricted use of projection and injection), the Toffoli gate $T$ is a universal gate. In other words, $\left\{ T \right\}$ is functionally complete.

Proof

Theorem

If duplication functions are allowed, $\left\{ \uparrow \right\}$ is functionally complete. In other words, the $\text{NAND}$ gate $\uparrow$ is a universal gate.

According to the theorem above, showing that projection, injection, and $T$ can be used appropriately to express the duplication function $\text{cl}$ and the $\text{NAND}$ gate completes the proof.

• Duplication Function

  $$\operatorname{cl} = p_{1} \circ T \circ \imath_{2} \circ \jmath_{1}$$

  Holds. First, calculating $T \circ \imath_{2} \circ \jmath_{1} (a)$ gives the following.

  $$T \circ \imath_{2} \circ \jmath_{1} (a) = T \circ \imath_{2} (a, 1) = T (a, 1, 0)$$

  Here, if $a = 1$, then $T(1, 1, 0) = (1, 1, 1)$; if $a = 0$, then $T(0, 1, 0) = (0, 1, 0)$, so the following holds.

  $$T(a, 1, 0) = (a, 1, a)$$

  Therefore, by taking $p_{1}$,

  $$p_{1} \circ T \circ \imath_{2} \circ \jmath_{1} (a) = p_{1} (a, 1, a) = (a, a) = \operatorname{cl}(a)$$

• $\text{NAND}$ Gate

  $$p_{0} \circ p_{1} \circ T \circ \jmath_{2} = \uparrow \\ p_{0} \circ p_{1} \circ T \circ \jmath_{2} (a, b) = a \uparrow b$$

  Holds. Calculating in order gives the following.

  $$\begin{align*} p_{0} \circ p_{1} \circ T \circ \jmath_{2} (a, b) &= p_{0} \circ p_{1} \circ T (a, b, 1) \\ &= p_{0} \circ p_{1} (a, b, (a \land b) \oplus 1) \\ &= p_{0} (a, (a \land b) \oplus 1) \\ &= (a \land b) \oplus 1 \\ &= \lnot(a \land b) = a \uparrow b \end{align*}$$

  The last line holds due to the properties of the $\text{XOR}$ gate.

■