Synthesizing Multi-Qubit Gates

The Toffoli (CCX) gate is the quantum AND: it flips its target only when both controls are $|1\rangle$. It is indispensable for oracles, arithmetic, and error correction — yet no superconducting or trapped-ion device implements a native three-qubit gate. Every Toffoli that runs on hardware has first been synthesized out of one- and two-qubit gates.

From CCX to CCZ

The first move is a conjugation identity you met earlier:

Sandwiching the target between Hadamards converts the doubly-controlled $X$ into a doubly-controlled $Z$. CCZ is symmetric and phase-only: it applies a $-1$ exactly to $|111\rangle$. That phase can be distributed among the three qubits as controlled $\pm\pi/4$ rotations, which is where the $T$ gates enter.

The seven-T construction

The textbook decomposition realizes the interior CCZ with six CNOTs and seven $\pi/4$-phase gates ($T$ and its inverse $T^\dagger$):

The alternating CNOT ladder routes the parity of the two controls onto the target, the $T$ and $T^\dagger$ gates imprint the $\pm\pi/4$ phases so they constructively combine only on $|111\rangle$, and the final $\mathrm{CNOT}$–$T$/$T^\dagger$–$\mathrm{CNOT}$ block cancels the unwanted relative phase between the two control qubits.

Why the order is delicate

Unlike a uniform superposition, this circuit cannot be reordered freely: the CNOTs and $T$ gates share qubits, so adjacent operations do not commute. Each $T$ must land between the right pair of CNOTs for the phases to interfere correctly. Get one gate out of place and the circuit still produces some unitary — just not the Toffoli. This is exactly why the grader checks the full $8\times 8$ matrix rather than a single output state.

Try it

Synthesize $\mathrm{CCX}$ with controls 0, 1 and target 2 using only h, t, tdg, and cx. The grader compares the complete three-qubit unitary up to global phase.

Sign in on the full site to ask questions and join the discussion.