Toffoli Gate

A three-qubit gate that flips the target only when both control qubits are |1>. Also known as the quantum AND gate.

The Toffoli gate (also called CCNOT or Controlled-Controlled-NOT) is a three-qubit gate that’s universal for classical reversible computation and important for quantum algorithms.

Definition

Two control qubits, one target qubit:

$∣ a, b, c ⟩ \to ∣ a, b, c \oplus (a \land b)⟩$

The target flips only when both controls are $∣1 ⟩$ .

Input	Output
$∥000 ⟩$	$∥000 ⟩$
$∥001 ⟩$	$∥001 ⟩$
$∥010 ⟩$	$∥010 ⟩$
$∥011 ⟩$	$∥011 ⟩$
$∥100 ⟩$	$∥100 ⟩$
$∥101 ⟩$	$∥101 ⟩$
$∥110 ⟩$	$∥111 ⟩$
$∥111 ⟩$	$∥110 ⟩$

Circuit Symbol

Control 1: ──●──
             │
Control 2: ──●──
             │
Target:    ──⊕──

Classical Reversible Computing

The Toffoli gate is universal for classical reversible computation:

AND: Set target to $∣0 ⟩$ , result is $a \land b$
NOT: Set both controls to $∣1 ⟩$
FANOUT: Can copy classical bits

Any classical circuit can be made reversible using Toffoli gates (with ancilla bits).

Quantum Universality

Toffoli + Hadamard is universal for quantum computing. However, Toffoli alone (without superposition-creating gates) cannot perform universal quantum computation.

Decomposition

A Toffoli can be decomposed into simpler gates:

──●────●────────●────●────●──
  │    │        │    │    │
──●────┼────●───┼────●────┼──
  │    │    │   │    │    │
──┼──T─X─T†─X─T─X─T†─X────┼──

This uses ~6 CNOT gates and several T gates, making it expensive on near-term hardware.

Applications

Quantum arithmetic: Addition, multiplication circuits
Grover’s oracle: Marking solutions in search
Reversible classical subroutines: Embedding classical functions in quantum algorithms
Quantum error correction: Syndrome extraction

Generalization

Multi-controlled NOT (MCX): $n$ control qubits, 1 target
Decomposition cost grows with number of controls

See also: CNOT Gate, Quantum Gate, Universal Gate Set, T Gate

Quantum Jargon Decoder