The Toffoli Gate
The Toffoli gate is a controlled-controlled-NOT that makes classical logic reversible and is a key primitive in quantum arithmetic.
A three-qubit gate
The Toffoli gate, or controlled-controlled-NOT (CCNOT), acts on three qubits: two controls and one target. It flips the target if and only if both controls are |1>, and otherwise leaves everything unchanged. It is the workhorse for embedding classical logic into reversible quantum circuits.
Truth table
| ctrl1 | ctrl2 | target-out |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
The table shown is for a target starting at 0: the output is the AND of the two controls. With the target at 1 the output is NAND. Because NAND is classically universal, Toffoli can reversibly compute any Boolean function.
Reversible classical logic
Classical AND is irreversible — you cannot recover two input bits from one output bit — so it cannot be a quantum gate directly. Toffoli fixes this by keeping the controls intact and writing the result into a fresh target qubit. This is how classical subroutines (adders, comparators, oracles) are lifted into quantum circuits without violating unitarity.
Universality
Toffoli plus Hadamard is universal for quantum computation, and Toffoli alone is universal for reversible classical computation. This makes it a natural bridge: the same gate that underlies reversible classical arithmetic also participates in fully quantum algorithms.
Cost and decomposition
Toffoli is not a native hardware gate on most platforms; it must be decomposed into one- and two-qubit gates, typically requiring several CNOTs and T gates. Because T gates are expensive in fault-tolerant schemes, the T-count of Toffoli decompositions is a focus of optimisation. Its cost is a major factor in the resource estimates for algorithms that do heavy arithmetic, such as Shor's.