1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
---
title: "Toffoli gate"
firstLetter: "T"
publishDate: 2021-04-09
categories:
- Quantum information
date: 2021-04-09T14:44:43+02:00
draft: false
markup: pandoc
---
# Toffoli gate
The **Toffoli gate** or **controlled-controlled-NOT (CCNOT) gate**
is a logic gate that is *reversible* (no information is lost)
and *universal* (all reversible logic circuits can be built using Toffoli gates).
It takes three input bits $A$, $B$ and $C$,
of which it returns $A$ and $B$ unchanged,
and flips $C$ if both $A$ and $B$ are true.
In circuit diagrams, its representation is:
<a href="toffoli.png">
<img src="toffoli.png" style="width:19%;display:block;margin:auto;">
</a>
This gate is reversible, because $A$ and $B$ are preserved,
and are all you need to reconstruct to $C$.
Moreover, this gate is universal,
because we can make a NAND gate from it:
<a href="nand.png">
<img src="nand.png" style="width:38%;display:block;margin:auto;">
</a>
A NAND is enough to implement every conceivable circuit.
That said, we can efficiently implement NOT, AND, and XOR using a single Toffoli gate too.
Note that NOT is a special case of NAND:
<a href="not.png">
<img src="not.png" style="width:32%;display:block;margin:auto;">
</a>
<a href="and.png">
<img src="and.png" style="width:35%;display:block;margin:auto;">
</a>
<a href="xor.png">
<img src="xor.png" style="width:35%;display:block;margin:auto;">
</a>
Using these, we can, as an example, make an OR gate
from three Toffoli gates,
thanks to the fact that $A \lor B = \neg (\neg A \land \neg B)$,
i.e. OR is NAND of NOT $A$ and NOT $B$:
<a href="or.png">
<img src="or.png" style="width:50%;display:block;margin:auto;">
</a>
Thanks to its reversibility and universality,
the Toffoli gate is interesting for quantum computing.
Its [quantum gate](/know/concept/quantum-gate/) form is often called **CCNOT**.
In the basis $\ket{A} \ket{B} \ket{C}$, its matrix is:
$$\begin{aligned}
\boxed{
\mathrm{CCNOT} =
\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}
}
\end{aligned}$$
If we apply this gate to an arbitrary three-qubit state $\ket{\psi}$,
it swaps the last two coefficients:
$$\begin{aligned}
\mathrm{CCNOT} \ket{\psi}
&= \mathrm{CCNOT} \big( c_{000} \ket{000} + c_{001} \ket{001} + c_{010} \ket{010} + c_{011} \ket{011} \\
&\qquad\qquad\quad\:\; c_{100} \ket{100} + c_{101} \ket{101} + c_{110} \ket{110} + c_{111} \ket{111} \big)
\\
&= c_{000} \ket{000} + c_{001} \ket{001} + c_{010} \ket{010} + c_{011} \ket{011} \\
&\quad\,\, c_{100} \ket{100} + c_{101} \ket{101} + c_{111} \ket{110} + c_{110} \ket{111}
\end{aligned}$$
## References
1. J.S. Neergaard-Nielsen,
*Quantum information: lectures notes*,
2021, unpublished.
|
