Gates & Circuits
Toffoli Gate
A three-qubit gate that flips a target qubit only when both control qubits are 1; the quantum version of AND.
Definition
The Toffoli gate, also called the controlled-controlled-NOT, has two control qubits and one target. The target flips only if both controls are 1. It is the reversible version of the AND operation, which makes it the key to running classical logic on a quantum computer. Arithmetic inside algorithms such as Shor's, and the oracles in Grover's search, are built out of Toffoli gates.
In depth
Classical computers use gates such as AND that discard information: from the output 0 you cannot tell which inputs produced it. Quantum gates must be reversible, so a quantum computer needs a version of AND that keeps its inputs. The Toffoli gate does that by writing the AND of the inputs into a third qubit while leaving the inputs unchanged. Toffoli, together with the ability to prepare a 1, is universal for reversible classical computation, which means any classical program can be run reversibly on a quantum computer.
This is why Toffoli gates fill quantum algorithm circuits. In Shor's algorithm, modular exponentiation is carried out by adders and multipliers built from Toffolis. In Grover's algorithm, an oracle that checks a condition is a reversible circuit of Toffolis that flips a flag qubit when the input satisfies the condition. Counting Toffoli gates is the standard way to estimate algorithm cost in cryptanalysis papers, for example in estimates of breaking RSA and elliptic curve cryptography.
On fault-tolerant hardware, the Toffoli gate is non-Clifford, so it is expensive. It costs about four T gates with ancillas in optimized constructions, or can be made from a prepared CCZ magic state. Compilers try to reduce Toffoli counts using tricks such as measurement-based uncomputation, which removes temporary values at half the cost, and by arranging arithmetic carefully.
Technical Definition
The Toffoli gate maps the basis state of qubits a, b, c to a, b, and c XOR the product of a and b. It is a permutation matrix on 8 basis states, reversible and self-inverse, and universal for reversible classical computation. A standard decomposition uses 6 CNOT gates and 7 T gates, together with Hadamards, or it can be implemented with relative-phase variants that cost fewer resources.
Visual Explanation: An Analogy
Picture a door that opens only when two keys are turned at the same time. The two controls are the keys and the target is the door. If both are turned, the door state flips, and if not, nothing happens, and you can always run it again to undo the flip.
Key facts
| Item | Detail |
|---|---|
| Size | Three qubits: two controls and one target |
| Action | Flips the target if and only if both controls are 1 |
| Classical analogue | Reversible AND, and with a constant, NAND |
| Standard decomposition | About 6 CNOT gates and 7 T gates, with optimized versions using 4 T gates and an ancilla |
| Invented | By Tommaso Toffoli in 1980 |
Where the idea comes from
Tommaso Toffoli described the gate in 1980 in work on reversible computing, and Charles Bennett had shown in 1973 that computation can be made reversible in principle. The gate became central to quantum computing because it is the smallest standard gate that makes reversible classical logic universal, and Barenco and coauthors showed in 1995 how to decompose it into two-qubit gates.
Real-World Use Cases
- Building adders, multipliers, and comparators for arithmetic in quantum algorithms.
- Implementing oracles that evaluate a Boolean function for Grover search.
- Performing classical conditional logic inside quantum error correction.
- Estimating algorithm cost as a Toffoli count in resource analyses.
How it differs from related ideas
- A CNOT has one control and flips the target, and a Toffoli has two controls.
- A classical AND loses information, and a Toffoli keeps the inputs and so is reversible.
- Toffoli and CCZ are equivalent up to Hadamard gates on the target.
Common Misconceptions
- The Toffoli gate is not a native operation on most hardware. It is compiled into one- and two-qubit gates.
- It is not a quantum-only gate. It is a classical reversible gate that also acts on superpositions.
- Toffoli alone cannot give a quantum speedup, since it is classical, and quantum advantage needs other gates such as Hadamard.
Frequently asked questions
What does the Toffoli gate do?
It flips a target qubit when both of its two control qubits are 1, otherwise it does nothing.
Why is it important?
It implements reversible AND, which is the basis of arithmetic and conditional logic in quantum algorithms.
How is it implemented on real hardware?
It is decomposed into single-qubit and CNOT gates, with T gates when error correction is used, and sometimes made natively on neutral-atom or ion platforms.
Related Terms
Keep exploring
- Algorithm: Shor's Algorithm
- Algorithm: Grover's Algorithm
- Hardware: Quantinuum H2