| Toffoli gate | |
|---|---|
| Name | Toffoli gate |
| Othernames | CCNOT, controlled-controlled-NOT |
| Type | Reversible logic gate |
| Introduced | 1980 |
| Inventor | Tommaso Toffoli |
| Gatesymbol | Toffoli |
Toffoli gate
The Toffoli gate is a three‑bit reversible logic gate that flips the state of a target bit conditional on the logical AND of two control bits. In quantum computing it is implemented as a three‑qubit controlled-controlled-NOT (CCNOT) unitary and serves as a key primitive for constructing reversible classical circuits inside quantum algorithms, embedding classical boolean logic into quantum computation and enabling universal reversible computation.
The Toffoli gate was introduced by Tommaso Toffoli in the study of reversible computation and later named after him. In classical reversible logic it maps basis states |a,b,c⟩ to |a,b,c ⊕ (a ∧ b)⟩, where a and b are control bits and c is the target bit. In the quantum setting the Toffoli gate is represented by a unitary operator acting on three qubits that preserves computational basis states in the same conditional fashion while being linear and unitary on superpositions. The gate is often denoted CCNOT and is widely used in constructions by Charles H. Bennett and Rolf Landauer relating thermodynamics and reversibility, and in algorithmic implementations such as arithmetic circuits used in Shor's algorithm.
As a matrix in the computational basis ordered |000⟩,...,|111⟩, the Toffoli gate is an 8×8 permutation matrix equal to the identity on the first six basis states and swaps |110⟩↔|111⟩ (i.e., flips the target when both controls are 1). The gate is reversible and unitary, with determinant +1. It belongs to the group generated by reversible classical gates and can be constructed from smaller gates: via a sequence of one‑ and two‑qubit gates it can be decomposed into CNOTs and single‑qubit rotations such as Hadamard and T gate (π/8 gate), or implemented using ancilla qubits to reduce depth. The Toffoli is an element of the Clifford+T synthesis target when decomposed for fault‑tolerant architectures; counting its T-count and T-depth is a common resource metric in circuit synthesis.
In circuit diagrams the Toffoli is depicted with two control dots connected to a target ⊕ symbol. Standard decompositions use at most six CNOTs and several single‑qubit rotations; optimized exact decompositions are known that trade off gate count, depth, and ancilla qubit usage. Alternative constructions embed classical reversible functions into quantum circuits using Toffoli networks for reversible arithmetic, adders, and modular exponentiation subroutines used in Shor's factoring algorithm. Synthesis techniques from Nielsen and Chuang and later works provide systematic methods to compile Toffoli into superconducting qubit and trapped ion native gatesets. The Toffoli gate also appears in reversible logic synthesis tools developed in groups such as MIT and IBM for mapping classical logic to quantum circuits.
Experimental realizations of Toffoli gates have been demonstrated across multiple platforms. In trapped ion systems groups at University of Innsbruck and NIST implemented three‑qubit Toffoli operations using multi‑pulse entangling interactions and native Molmer–Sørensen gates. In superconducting qubits platforms, teams at IBM and Rigetti reported three‑qubit gates approximating Toffoli via microwave‑driven interactions or decomposed sequences of CZ gates and single‑qubit rotations. Photonic implementations used linear optics and ancilla photons in experiments by groups at University of Vienna and University of Bristol to realize nondeterministic Toffoli operations. Solid‑state spin systems such as NV centers in diamond and silicon quantum dot setups have also demonstrated controlled‑controlled operations or equivalent classical reversible logic primitives. Reported fidelities vary by platform and methodology; achieving fault‑tolerant thresholds typically requires further error mitigation and gate optimization.
The Toffoli gate is universal for classical reversible computation: any reversible Boolean function can be composed from Toffoli gates (possibly with ancilla bits). In quantum computation, the set of all single‑qubit gates together with the Toffoli is computationally universal for quantum circuits that implement classical reversible logic embedded in quantum algorithms, though full quantum universality typically cites sets like Clifford+T or CNOT plus arbitrary single‑qubit rotations. The Toffoli plays a central role in reversible arithmetic, logical controlled operations, and oracle constructions in algorithms such as Grover's algorithm and circuit designs for arithmetic required by Shor's algorithm. Its status as a classical reversible universal gate links it to studies in computational complexity, such as space‑bounded reversible computation and reversible implementations of Turing machine transitions.
Implementing Toffoli fault‑tolerantly is challenging because it is not generally a transversal gate in common quantum error correction codes like the surface code or concatenated code families. Fault‑tolerant implementations therefore rely on techniques such as gate teleportation, magic‑state injection for non‑Clifford operations, or synthesis into sequences of fault‑tolerant primitives with controlled T gate resource consumption. Ancilla‑assisted constructions and verified ancilla preparation reduce logical error rates at the cost of overhead in qubits and operations; several protocols for fault‑tolerant Toffoli use prepared multi‑qubit resource states distilled by Bravyi–Kitaev style magic‑state distillation. Optimizing Toffoli's T-count and ancilla overhead remains important for scalable implementations on architectures pursuing quantum advantage.
Category:Quantum gates Category:Reversible computing