Transformation-Based Synthesis

Cycle decomposition proved that every permutation has a circuit — at a bruising price in gates. The transformation-based algorithm of Miller, Maslov and Dueck (2003), known to everyone in the field as MMD, gets to the same destination far more cheaply, and its idea is disarmingly simple: don't build the circuit — repair the truth table. Apply gates to the table until it becomes the identity; the gates you used, read backwards, are your circuit. It is the synthesis-world version of solving a Rubik's cube by scrambling it back to solved and writing down your moves in reverse.

The algorithm in five lines

Given a reversible truth table for f on n wires, walk the rows in increasing input order 000, 001, 010, \ldots At each row i, let v be the row's current output value:

if v = i, the row is already correct — move on;
otherwise apply gates to the entire output column that turn v into i:
- set each bit that is 1 in i but 0 in v, using a Toffoli-family gate whose controls sit on the 1-bits of v;
- clear each bit that is 1 in v but 0 in i, using a gate whose controls sit on the 1-bits of i;
when every row is fixed the table is the identity. The collected gate list, applied to outputs, computes f^{-1} — so the reversed list is the circuit for f.

The control discipline is the whole trick: gates controlled that way can never disturb a row that has already been repaired. We will see exactly why after the worked example.

Worked example: the 3-bit decrementer

Target: f(x) = x - 1 \bmod 8 on bits abc (so 000 \to 111, 001 \to 000, and so on). Here is the full run — the output column after each row's repair:

input	f	after row 000	after row 001	after row 010	after row 011
000	111	000	000	000	000
001	000	111	001	001	001
010	001	110	110	010	010
011	010	101	011	111	011
100	011	100	100	100	100
101	100	011	101	101	101
110	101	010	010	110	110
111	110	001	111	011	111

Row by row, the gate choices:

Row 000: v = 111. Clear all three bits; controls = 1-bits of i = 000, i.e. none — three plain NOTs (a, b, c). Every output gets XORed with 111.
Row 001: v = 111, target 001. Clear bits a and b; controls = 1-bits of i, i.e. bit c — two CNOTs, c \to a and c \to b.
Row 010: v = 110, target 010. Clear bit a; control on bit b — one CNOT b \to a.
Row 011: v = 111, target 011. Clear bit a; controls on bits b, c — one Toffoli (b, c \to a).
Rows 100–111: already correct — the run is over after just 7 gates. (Compare dozens by cycle decomposition.)

Reverse, and read off the circuit

The seven gates were applied to the output side, so together they compute f^{-1}. Reversing the list (every NCT gate is its own inverse) gives the circuit for f: Toffoli (b,c \to a), CNOT (b \to a), CNOT (c \to b), CNOT (c \to a), then NOT c, NOT b, NOT a. Watch it assemble:

Spot-check the row 111: the Toffoli fires (b=c=1) giving 011; CNOT b \to a gives 111; CNOT c \to b gives 101; CNOT c \to a gives 001; the NOTs give 110. Indeed 7 - 1 = 6. ✓

This is the load-bearing beam of MMD, and it is a one-line inequality. A Toffoli-family gate whose controls sit on the 1-bits of a pattern p only fires on states whose pattern contains all those 1s — states that are supersets of p. But a bit pattern that contains all the 1-bits of p is, as a binary number, at least p. Now look at the two control choices: at row i the controls sit on the 1-bits of v (the current output, and v \ge i, since all values below i are already claimed by the fixed rows) or on the 1-bits of i itself. Either way the gate can only touch output values \ge i — and the already-repaired rows hold the values 0, 1, \ldots, i-1, all safely below. Processing rows in increasing order plus 1-bit control discipline = earlier work is untouchable. That is the entire correctness proof.

Bidirectional refinement

A free upgrade: the truth table has two ends. Gates applied to the output column build the circuit from its output end inwards (they get reversed); but you can equally apply a gate to the input column — permuting which input maps to which output — and such gates stack up at the circuit's input end, in the order found. Bidirectional MMD looks at each unfixed row and asks: is it cheaper to drag the output value v to i, or to drag the input pattern toward the row whose output is already i? It takes the cheaper move, working from both ends toward the middle. On benchmarks this routinely shaves 20–30% off the gate count — the classic "meet in the middle" dividend.

The single most common MMD blunder: forgetting the reverse. The gates you collect act on the output column, undoing f — as listed, they are a circuit for f^{-1}, not f. For the final circuit you must emit them back to front. (In our example the three NOTs were found first but sit last in the finished decrementer.) If you ever run your synthesised circuit and get the inverse permutation of the one you wanted, you know exactly what happened — and since NCT gates are self-inverse, the fix is pure bookkeeping: flip the list, not the gates.