The Toffoli gate (CCX or Controlled-Controlled-NOT) is a three-qubit gate that applies an X (NOT) gate to the target qubit only when both control qubits are in state |1⟩. It is named after Tommaso Toffoli who introduced it in 1980. The Toffoli gate is universal for classical reversible computation — any classical Boolean circuit (AND, OR, NOT) can be implemented reversibly using Toffoli gates. Combined with the Hadamard gate, it becomes universal for quantum computation. Since it is a 3-qubit operation, Toffoli gates are expensive on real hardware: they are typically decomposed into 6 CNOT gates and several single-qubit gates during transpilation. Toffoli gates appear frequently in quantum arithmetic, oracle construction for Grover's algorithm, and classical function simulation.
Related Terms
Quantum Gate
GatesA unitary operation that transforms the state of one or more qubits.
CNOT Gate
GatesControlled-NOT — a two-qubit gate that flips the target qubit when the control qubit is |1⟩.
Pauli Operators
GatesThe fundamental single-qubit gates X, Y, Z — forming the basis for all quantum operations.
Transpilation
HardwareThe process of compiling a quantum circuit into the native gate set and qubit connectivity of a specific device.