Synthesis algorithms — MMD, ESOP translation, ladder decompositions with their ancilla trade-offs — hand you a correct circuit, not a good one. Their output is a rough draft, full of gates that undo each other, gates that could slide past one another, and little sub-patterns with cheaper equivalents. Post-synthesis optimization is the editing pass: a toolbox of local rewrites that preserve the permutation while shrinking the cost metrics. The three tools, in order of sophistication: cancellation, commutation, and template matching.

Tool 1: cancellation

Every NCT gate is self-inverse: G \cdot G = I. So two identical, adjacent gates annihilate — delete both, the permutation is unchanged, the gate count drops by two. Synthesised circuits are full of these: MMD's row-by-row repairs and cycle decomposition's sandwich bread routinely leave matching pairs face to face, especially after blocks are concatenated. Cancellation is trivial to check and free to apply, which is why every optimizer runs it first — and, as we will see, again after every other rewrite.

Tool 2: commutation

Cancellation only fires on adjacent pairs, so the second tool creates adjacency: rules for when two neighbouring gates may swap places without changing the circuit. The classification is a pleasant exercise in thinking about who reads and who writes each wire:

The classic counterexample for the last row: NOT on wire a versus CNOT (a \to b). As "NOT then CNOT" the target receives b \oplus \bar a; as "CNOT then NOT" it receives b \oplus a. Different functions — no swap allowed. But NOT on b (the target) slides through the same CNOT freely: flipping the target before or after XORing a onto it lands in the same place.

Tool 3: templates and peephole rewriting

The heavyweight tool: a template is a known circuit identity — a short gate sequence equal to a cheaper one. An optimizer slides a small window (a "peephole") along the cascade, matches templates (using commutation to herd the participating gates together), and rewrites. Here is a classic, worth working through because the algebra is two lines. Take the window: Toffoli (a,b \to c), NOT a, Toffoli (a,b \to c), NOT a. The two Toffolis together XOR onto c both ab (first, with a as supplied) and \bar a b (second, with a flipped), while the NOTs cancel each other on wire a:

Four gates — two of them expensive Toffolis — equal one CNOT (b \to c):

A template library full of identities like this (and their mirror images, and their control-permuted variants) is the core of production reversible-circuit optimizers. Each rewrite can expose fresh cancellations, so the passes loop until nothing fires — a fixpoint.

Try it: a tiny peephole pass

The simplest possible optimizer — cancel adjacent identical gates, repeat until stable — is a dozen lines. Watch how removing one pair brings another pair together:

The first pass removes the CNOT pair and the NOT pair; only then do the two Toffolis become adjacent and cancel on the second pass. Six gates, net effect: nothing at all. Real optimizers interleave commutation and template passes in the same loop — but the fixpoint skeleton is exactly this.

Benchmarks, and the metric that pays the bills

How do you know your optimizer is any good? The field's shared yardstick is RevLib — a public library of reversible benchmark functions and circuits (adders, cipher pieces, hidden-weight-bit functions…) with the best known costs on record. Publishing a synthesis paper without RevLib numbers is like claiming a sprint record without a stopwatch. And which metric should the optimizer chase? Increasingly, the one downstream: on fault-tolerant quantum hardware the crushing expense is the T gate, with a Toffoli costing about 7 of them — so a rewrite that trades one Toffoli for three CNOTs is an excellent deal there, even though the raw gate count went up. Optimization is always toward a cost model; change the price list and the best circuit changes too.