Lemma: Clean-work transposition synthesis

Let $N\ge 3$. A permutation of $N$ logical bits that is a product of $Q$ specified transpositions has a NOT–CNOT–Toffoli realization using $N-2$ clean work bits and at most

gates. On work-zero inputs, its logical action is the permutation and work returns to zero.

Proof. Join the endpoints of one transposition by a shortest Hamming path of length $h\le N$. Exchange successive path words going forward, then going backward along all but the final edge. This uses $2h-1\le 2N-1$ adjacent-word transpositions and restores every intermediate path word.

An adjacent-word transposition flips its differing bit controlled on one specified pattern of the other $N-1$ bits. Conjugating negative controls by NOT gates costs at most $2(N-1)$ gates. Compute the conjunction of the positive controls into $N-2$ clean work bits by a Toffoli chain, use one CNOT to flip the target, and reverse the chain. This costs another $2(N-2)+1$ gates and restores work. The total is $4N-5<4N$ per adjacent exchange. Summing proves (eq:synthesis-bound).