Controlled Gates and the Toffoli

Here is a strange promise: a quantum computer can run every ordinary logic circuit your laptop can — AND, OR, NOT, the lot — and do it while obeying the one rule quantum mechanics never bends, that every operation be reversible. The bridge that makes this possible is a single three-qubit gate, the Toffoli. To reach it we first generalise the one gate you already know, the CNOT: it is the smallest member of a whole family of controlled gates, where one qubit decides whether something happens to another.

Controlled-U: "do it only if the control is on"

Take any single-qubit gate U — a 2\times 2 unitary. The controlled-U gate acts on two qubits, a control and a target, with one rule: apply U to the target only when the control is |1\rangle; leave the target untouched when the control is |0\rangle. In the ordered basis |00\rangle, |01\rangle, |10\rangle, |11\rangle this is a block-diagonal matrix — identity on the control-0 block, and U on the control-1 block:

\mathrm{C}U \;=\; \begin{bmatrix} I & 0 \\ 0 & U \end{bmatrix} \;=\; \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & u_{11} & u_{12} \\ 0 & 0 & u_{21} & u_{22} \end{bmatrix}, \qquad U = \begin{bmatrix} u_{11} & u_{12} \\ u_{21} & u_{22} \end{bmatrix}.

Slot different gates into U and you get the whole family. Choosing the bit-flip U = X gives \mathrm{C}X — that is exactly the CNOT. Choosing U = Z gives controlled-Z (which flips the phase of only |11\rangle), and a phase gate gives a controlled-phase. Same skeleton every time; only the bottom-right block changes.

The Toffoli gate: two controls, one target

The Toffoli gate — also written CCNOT, "controlled-controlled-NOT" — is the natural next step: two control qubits and one target. Its rule is a single sentence: flip the target if and only if both controls are |1\rangle. On all seven other input strings the three qubits pass straight through unchanged. In a circuit it is drawn as two solid control dots joined to a target \oplus:

Because it acts on three qubits it is an 8\times 8 matrix, and because it only ever shuffles basis strings among themselves it is a permutation matrix — every row and column has a single 1. That permutation is trivial: it is the identity on six strings and swaps just the last two, |110\rangle \leftrightarrow |111\rangle (the two where both controls are on, so the target flips 0 \leftrightarrow 1).

Worked example 1: the Toffoli truth table

Write the three input bits as c_1 c_2 t (two controls, then target) and apply the rule "target flips iff c_1 = c_2 = 1". Only the last two rows do anything:

\begin{array}{ccc|ccc} c_1 & c_2 & t & c_1 & c_2 & t' \\ \hline 0&0&0 & 0&0&0 \\ 0&0&1 & 0&0&1 \\ 0&1&0 & 0&1&0 \\ 0&1&1 & 0&1&1 \\ 1&0&0 & 1&0&0 \\ 1&0&1 & 1&0&1 \\ 1&1&0 & 1&1&\mathbf{1} \\ 1&1&1 & 1&1&\mathbf{0} \end{array}

The controls are copied out unchanged; only the target's new value t' = t \oplus (c_1 \wedge c_2) can differ, and it does so on exactly the two bold rows. Read the output column and you see the |110\rangle \leftrightarrow |111\rangle swap and nothing else — a genuine permutation of the eight strings.

Worked example 2: an AND gate from a Toffoli

Here is why the Toffoli matters. Feed it two data bits a, b as the controls and initialise the target to |0\rangle. The output target is

t' \;=\; 0 \oplus (a \wedge b) \;=\; a \wedge b \;=\; a \cdot b.

The fresh |0\rangle qubit comes out carrying the logical AND of the two inputs: it becomes 1 only for a = b = 1. So \text{Toffoli}(a, b, 0) = (a, b, a\wedge b) is a reversible AND gate — the controls survive so nothing is thrown away, and the answer lands on the ancilla. Swap that ancilla's start to |1\rangle instead and you compute 1 \oplus (a\wedge b), the NAND — and NAND alone is enough to build every Boolean function.

A quantum computer must make every step reversible and unitary — but ordinary logic is neither. An AND gate destroys information (given output 0 you cannot recover which of three inputs produced it), so it can never be a unitary on its own. The Toffoli is the fix: it embeds any irreversible Boolean function inside a bigger, reversible one by carrying spare ancilla bits that keep enough of the inputs around to run the computation backwards. Since AND, NOT, OR and fan-out all reduce to Toffolis, every classical program can be recompiled into a reversible circuit of Toffoli gates — and a reversible circuit is exactly a quantum circuit made of permutation gates. That is the precise sense in which a quantum computer contains an entire classical one for free, before a single superposition is ever used.

Two traps. First, reversibility forbids overwriting: an AND has two inputs and one output, but a reversible gate must have as many outputs as inputs, so you cannot simply "replace" a, b with a \wedge b. You must supply a fresh ancilla qubit to receive the answer and accept that the controls stay around as garbage bits — bookkeeping that reversible computing can never escape (you clean it up later by uncomputing). Second, the "reversible AND" story only holds when the controls are genuine bits, |0\rangle or |1\rangle. Feed the Toffoli a control in superposition and it does not "compute a value" — it entangles the target with the controls (e.g. controls in |{+}\rangle|{+}\rangle spread the target across a correlated three-qubit state). Same gate, wholly quantum behaviour.