Toffoli

The Toffoli gate, named after Tommaso Toffoli, is a three-qubit reversible gate commonly described as the controlled-controlled-not (CCNOT) gate. It maps the input state |a,b,c> to |a,b,c XOR (a AND b)>, meaning the third qubit (the target) is flipped only when both of the first two qubits (the controls) are in the state 1. All other basis states remain unchanged.

In classical reversible computing, the Toffoli gate is universal: any reversible Boolean function can be constructed using Toffoli gates (often together with NOT gates). In quantum computing, the Toffoli gate serves as a non-Clifford gate that enables universal quantum computation when combined with single-qubit operations. It can be implemented by decomposing it into a sequence of simpler quantum gates, such as CNOTs and single-qubit rotations; multiple decompositions exist, including Clifford+T based implementations.

Applications of the Toffoli gate appear in quantum algorithms and circuits that require a conditional operation on a target qubit based on two control qubits, such as arithmetic circuits, digitized logic blocks, and certain error-correction procedures. As a fundamental three-qubit primitive, it also serves as a standard building block for more complex reversible and quantum circuits, illustrating the crossover between classical reversible logic and quantum computation.