Expand knowledge base

1 files changed, 93 insertions, 0 deletions

diff --git a/content/know/concept/toffoli-gate/index.pdc b/content/know/concept/toffoli-gate/index.pdc
new file mode 100644
index 0000000..84e7656
--- /dev/null
+++ b/content/know/concept/toffoli-gate/index.pdc
@@ -0,0 +1,93 @@
+---
+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 in quantum computing,
+where it is often referred to as the CCNOT gate.
+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}$$