Table of Contents
CCX (Toffoli) gate
CCX gate (doubly-controlled X, also called Toffoli gate or CCNOT) is a three-qubit gate that flips the target qubit if and only if both control qubits are . It was introduced by Tommaso Toffoli in 1980 and is the key building block for reversible classical computation inside a quantum circuit.
The gate implements the reversible Boolean operation , where is XOR and is AND. Its matrix is the identity with the last two rows swapped (basis ordered through ):
Classical universality
The CCX gate alone is classically universal — any Boolean function can be computed reversibly using only CCX gates. Setting gives AND: . Setting gives NOT: . AND and NOT are a complete classical gate set.
Circuit decomposition
The CCX gate can be decomposed into six CX gates and several single-qubit gates. It is its own inverse: . CCX gates appear in reversible arithmetic circuits (adders, multipliers) embedded inside quantum algorithms, and in quantum error correction as controlled-controlled operations.
