Categories: Quantum information.

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

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

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:

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

Thanks to its reversibility and universality,
the Toffoli gate is interesting for quantum computing.
Its quantum gate form is often called **CCNOT**.
In the basis $\ket{A} \ket{B} \ket{C}$, its matrix is:

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

- J.S. Neergaard-Nielsen,
*Quantum information: lectures notes*, 2021, unpublished.