Source-verifiedLevel 3

Toffoli Gate

The Toffoli gate (CCNOT) is a three-qubit gate that flips the target qubit only when both control qubits are |1⟩, serving as a universal gate for classical reversible computation.

What it means

The Toffoli gate, also called the controlled-controlled-NOT (CCNOT) gate, is a three-qubit gate where the target qubit is flipped if and only if both control qubits are in state |1⟩.It is universal for classical reversible computation, meaning any classical Boolean function can be implemented using Toffoli gates.In quantum computing, it can be decomposed into six CNOT gates and several single-qubit gates.The Toffoli gate is central to quantum arithmetic circuits, quantum error correction, and the implementation of quantum oracles in algorithms like Grover's search.

Everyday analogy

The Toffoli gate is like a vault that requires two keys to open -- the target changes only when both controls agree.
Think of it as a two-person authorization system -- both managers must approve before the action (bit flip) occurs.

Common misconceptions

  • The Toffoli gate is NOT a native gate on most quantum hardware -- it must be decomposed into elementary gates.
  • The Toffoli gate alone is NOT universal for quantum computing -- it needs supplementation with gates that can create superposition.

Key takeaways

  • The Toffoli gate flips the target when both controls are |1⟩.
  • Universal for classical reversible computation.
  • Decomposed into 6 CNOT + single-qubit gates on hardware.

Check your understanding

What is the output of the Toffoli gate on |110⟩?

  1. A.|110⟩
  2. B.|111⟩
  3. C.|100⟩
  4. D.|010⟩
Show the answer

Answer: B. |111⟩

Why: Both controls are |1⟩, so the target (third qubit) flips from |0⟩ to |1⟩: |110⟩ → |111⟩.

Builds on

QubitCNOT GatePauli-X Gate

Primary source: Fredkin & Toffoli, Conservative logic, Int. J. Theor. Phys. 21, 219 (1982), doi:10.1007/BF01857727

Original: Toffoli, Reversible Computing, MIT/LCS/TM-151 (1980).

Learn it hands-on

This concept is part of a 46-level curriculum with an interactive simulator and Lumen, a tutor whose answers are verified before you see them. Levels 1–5 are free.

Start freeSee the curriculum