logo

Toffoli/CCNOT Gate

Toffoli/CCNOT Gate

Definition1

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.


  1. Kim Young-hoon and Heo Jae-seong, Quantum Information Theory (2020), pp. 89-93 ↩︎