Toffoli Gate (CCX) | Universal Reversible Classical & Quantum Gate
Quick Technical Answer:
The Toffoli gate (Controlled-Controlled-NOT or CCX) is a 3-qubit gate that flips the target qubit if and only if both control qubits are in state |1⟩: CCX|c1, c2, t⟩ = |c1, c2, t ⊕ (c1 · c2)⟩. It is universal for reversible classical computation.
Formula / Unitary:
CCX|1, 1, t\rangle = |1, 1, \neg t\rangle, \quad CCX|c_1, c_2, t\rangle = |c_1, c_2, t\rangle \text{ if } c_1 c_2 = 0
Simulate this in Itachi Quantum Studio
Inspect state amplitudes, 3D Bloch sphere vector, and OpenQASM code live.
Fault-Tolerant Decomposition into Clifford + T
On physical quantum processors with only 2-qubit native gates, the Toffoli gate decomposes into a minimum of 6 CNOT gates and 7 T/Tdg gates (or 4 T gates using ancilla assistance), making it a high-cost operation in fault-tolerant quantum algorithms.
Frequently Asked Questions
Why is the Toffoli gate important for Shor's algorithm?
Shor's algorithm requires modular arithmetic (addition and modular exponentiation), which is constructed entirely from reversible classical logic networks of Toffoli and CNOT gates.