CCX gate (Toffoli)

CCX (also Toffoli or Controlled-Controlled-X) is a three-qubit gate: flips the target qubit if both control qubits are $|1\rangle$. The quantum AND gate and is universal for reversible classical computation.

Action: $|c_1 c_2 t\rangle \to |c_1 c_2 (t \oplus c_1 c_2)\rangle$ where $c_1, c_2$ are controls and $t$ is target. Flips target only if both controls are 1.

$$\text{CCX} = \text{Toffoli} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}$$

Basis state mapping: $|abc\rangle \to |ab(c \oplus (a \wedge b))\rangle$. Swaps $|110\rangle \leftrightarrow |111\rangle$.

• Self-inverse: $\text{CCX}^2 = I$
• Universal: CCX alone is universal for reversible classical computation (can build AND, NAND, etc.)
• Quantum universal (with Hadamard): CCX + single-qubit gates form universal quantum gate set
• Reversible: implements reversible classical logic

• Quantum arithmetic: addition, subtraction, multiplication in quantum algorithms
• Classical simulation: Deutsch-Jozsa and related algorithms
• Reversible computing: designing reversible classical circuits
• Error correction: appears in quantum error correction codes

• Gate cost: ~6 CX gates + ~10 single-qubit gates
• Complexity: expensive operation; avoid when possible
• Note: complex multi-gate sequence (standard decomposition lengthy)

• Superconducting qubits: via gate decomposition; ~30–50 ns for single CCX or longer for full decomposition
• Trapped ions: scalable decomposition via laser interactions
• Photonic: probabilistic schemes or post-selection
• Development: some platforms creating native CCX implementations

• CSWAP (Fredkin): swaps two qubits if third is $|1\rangle$; also universal for reversible classical computation