Lemma: Exact reversible synthesis

A permutation of $N$ logical bits consisting of $q$ specified transpositions can be implemented using NOT, CNOT, and Toffoli gates, with $N-2$ clean work bits returned to zero. For the transpositions above, a sufficient gate bound is

Proof. Connect the two words of a transposition by a shortest Hamming path of length $k\le N$. The endpoint transposition is a product of $2k-1$ adjacent-word transpositions along that path.

An adjacent-word transposition is a NOT on the differing bit controlled on the specified pattern of the other $N-1$ bits. Negative controls are obtained by conjugating the relevant controls with NOT gates. The positive multiple-control NOT is implemented by computing the control conjunction into clean work bits with Toffoli gates, performing the target flip, and reversing the conjunction computation. At most $N-2$ work bits suffice. For $N\ge 3$, fewer than $4N$ elementary gates suffice for each adjacent-word transposition, including the NOT conjugations.

Applying this construction to all $q$ transpositions gives the bound. Every conjunction computation is uncomputed, so the work bits return to zero.