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 , and , of which it returns and unchanged, and flips only if both and are true. In circuit logic diagrams, its representation is:
This gate is reversible because and 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 , i.e. OR is NAND of NOT and NOT :
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 , its matrix is:
If we apply this gate to an arbitrary three-qubit state , it swaps the last two coefficients:
- J.S. Neergaard-Nielsen, Quantum information: lectures notes, 2021, unpublished.