summaryrefslogtreecommitdiff
path: root/source/know/concept/toffoli-gate/index.md
blob: b8caba1fe252ccfb982cd553ea7c50d5c0c8035a (plain)
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
---
title: "Toffoli gate"
sort_title: "Toffoli gate"
date: 2021-04-09
categories:
- Quantum information
layout: "concept"
---

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$$ only if both $$A$$ and $$B$$ are true.
In circuit logic diagrams, its representation is:

{% include image.html file="toffoli.png" width="19%"
    alt="Toffoli gate symbol" %}

This gate is reversible because $$A$$ and $$B$$ are preserved,
and it is universal because we can make a NAND gate from it:

{% include image.html file="nand.png" width="38%"
    alt="NAND gate made of Toffoli gate" %}

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:

{% include image.html file="not.png" width="32%"
    alt="NOT gate made of Toffoli gate" %}

{% include image.html file="and.png" width="35%"
    alt="AND gate made of Toffoli gate" %}

{% include image.html file="xor.png" width="35%"
    alt="XOR gate made of Toffoli gate" %}

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$$:

{% include image.html file="or.png" width="50%"
    alt="OR gate made of Toffoli gates" %}

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.