Permutations and Reversible Functions

Before you can synthesise a reversible circuit, you have to know exactly what you are synthesising. Here is the beautiful answer: a reversible function on n bits is nothing more or less than a shuffle of a deck of 2^n cards. The cards are the bit patterns 00\ldots0 through 11\ldots1; a reversible function deals every pattern to a new position, no two patterns to the same place. In other words, the reversible n-bit functions are precisely the permutations of a 2^n-element set — the symmetric group S_{2^n}. Everything you know about permutation groups — cycles, transpositions, parity, composition — instantly becomes a fact about circuits.

Counting the targets

How many reversible functions are there on n bits? A permutation of 2^n states can send the first state to any of 2^n places, the second to any of the remaining 2^n - 1, and so on:

\#\{\text{reversible functions on } n \text{ bits}\} = (2^n)!

n	states 2^n	reversible functions (2^n)!
1	2	2! = 2
2	4	4! = 24
3	8	8! = 40{,}320
4	16	16! \approx 2.09 \times 10^{13}

The explosion is the whole drama of synthesis: on just 4 wires there are twenty trillion target functions, and you must reach every one of them with cascades built from a three-gate library. No lookup table will ever be big enough — you need algorithms, and those are the next four lessons.

Gates in cycle notation

Since gates are permutations, we can write them in cycle notation — listing the states they actually move. Take the CNOT (control first bit, target second) on 2 wires. It maps 00 \to 00, 01 \to 01, 10 \to 11, 11 \to 10: two fixed points and one swap. As a permutation it is the single transposition (10\;\;11).

The same game for the other library gates, on their own wires:

NOT on 1 wire: (0\;\;1) — one transposition.
CNOT on 2 wires: (10\;\;11) — one transposition.
Toffoli on 3 wires: it moves only the states where both controls are 1, so it is the single transposition (110\;\;111) — the other six states are fixed points.

And composition is multiplication: a cascade of gates computes the product of their permutations. Running the circuit for g and then the circuit for h computes the composite h \circ g — the group operation of S_{2^n}, performed in copper and silicon.

Wire count changes the cycle type

Here is a subtlety that trips up nearly everyone. "CNOT is a transposition" was a statement about CNOT on its own two wires. Put the same CNOT on wires 1 and 2 of a 3-wire circuit and the spectator wire doubles everything: the gate now swaps 100 \leftrightarrow 110 and 101 \leftrightarrow 111 — a product of two disjoint transpositions, once for each value of the untouched bit. In general a gate acting on k wires inside an n-wire circuit repeats its cycle structure 2^{\,n-k} times, once per setting of the spectator bits.

Why care? Because of parity. Recall that every permutation is either even or odd — expressible as an even or odd number of transpositions — and that a product of even permutations is always even. Now count for each library gate on n wires:

Gate	transpositions on n wires	parity for n \ge 4
NOT (1 wire)	2^{\,n-1}	2^{\,n-1} \ge 8: even
CNOT (2 wires)	2^{\,n-2}	2^{\,n-2} \ge 4: even
Toffoli (3 wires)	2^{\,n-3}	2^{\,n-3} \ge 2: even

The parity obstruction

On n \ge 4 wires, every NOT, CNOT and Toffoli gate is an even permutation of the 2^n states — each repeats a transposition 2^{\,n-k} \ge 2 times;
hence every NCT cascade on n \ge 4 wires computes an even permutation: the library generates exactly the alternating group A_{2^n}, only half of S_{2^n};
an odd permutation (a single transposition of two patterns, say) on n \ge 4 wires therefore cannot be built from NCT gates on those wires alone — you must add an ancilla wire, on which the same target becomes an even permutation of the doubled state space and synthesis goes through;
on n \le 3 wires there is no obstruction: NOT (n=1), CNOT (n=2) and Toffoli (n=3) acting on all the wires are single transpositions — odd — and the library generates all of S_{2^n}.

This is a genuine no-go theorem, proved with nothing but the parity homomorphism from your permutation-groups toolkit — and it is the first place synthesis forces an ancilla on you. Whenever a synthesis paper says "realisable with at most one ancilla line", this obstruction is the reason the ancilla is there.

It sounds scandalous: on 4 wires the NCT library reaches only 16!/2 \approx 10^{13} of the 16! reversible functions — exactly half, the alternating group A_{16}. But the fix costs almost nothing. Add a single ancilla wire carrying a constant 0: your target permutation, viewed on the 32-state doubled space, repeats itself once for each ancilla value and is therefore even — and now it is reachable, with the ancilla returned to 0 at the end. One spare wire converts "impossible" into "routine". It is a first taste of a theme that dominates the rest of this module: workspace is a currency, and small amounts of it buy structural miracles.

The transposition (110\;\;111) does not mean "swap wires" or "swap bits 110 and 111". The entries in a cycle are entire bit patterns — points of the 2^n-element state space. (110\;\;111) says: if the three wires jointly hold 110, they now hold 111, and vice versa; all six other patterns pass through untouched. Mixing up the two pictures — permuting wires versus permuting states — is the classic error in this subject. (Permuting wires is also a reversible operation, but a far more special one: there are only n! of those against (2^n)! of these.)