Categories: Quantum information.

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:

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

\[\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}\]

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

© Marcus R.A. Newman, a.k.a. "Prefetch".
Available under CC BY-SA 4.0.