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$ |
|
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
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.
■
Kim Young-hoon and Heo Jae-seong, Quantum Information Theory (2020), pp. 89-93 ↩︎