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 AA, BB and CC, of which it returns AA and BB unchanged, and flips CC only if both AA and BB are true. In circuit logic diagrams, its representation is:

Toffoli gate symbol

This gate is reversible because AA and BB are preserved, and it is universal because we can make a NAND gate from it:

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:

NOT gate made of Toffoli gate

AND gate made of Toffoli gate

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∨B=¬(¬A∧¬B)A \lor B = \neg (\neg A \land \neg B), i.e. OR is NAND of NOT AA and NOT BB:

OR gate made of Toffoli gates

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 ∣A⟩∣B⟩∣C⟩\ket{A} \ket{B} \ket{C}, its matrix is:

CCNOT=[1000000001000000001000000001000000001000000001000000000100000010]\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:

CCNOT∣ψ⟩=CCNOT(c000∣000⟩+c001∣001⟩+c010∣010⟩+c011∣011⟩+   c100∣100⟩+c101∣101⟩+c110∣110⟩+c111∣111⟩)=c000∣000⟩+c001∣001⟩+c010∣010⟩+c011∣011⟩+  c100∣100⟩+c101∣101⟩+c111∣110⟩+c110∣111⟩\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.