Lemma: Forward-domain permutation completion

Let $H\ge 1$, $D\subseteq \{0,1{\}}^H$, and $f:D\to \{0,1{\}}^H$ be deterministic. Suppose an allocated stage field separates designated input and output sets, so that

are disjoint. Put $N=2H$.

There is a permutation realizing

For $N\ge 3$, NOT, CNOT, and Toffoli gates implement it on clean-work inputs with at most $N-2$ additional work bits and

elementary gates. Work returns to zero. For $N=2$, no work bits are needed and the same bound holds. An adjacent exchange on a one-bit register, when needed in another encoding, is a single NOT.

Proof. Retaining $x$ makes the designated output map injective. Transpose each disjoint pair

and fix all other words. This defines a permutation.

For one transposition, choose a shortest Hamming path $v_0,\dots ,v_{\ell }$, with $\ell \le N$. Its endpoint exchange is

using $2\ell -1\le 2N-1$ adjacent-word exchanges.

An adjacent exchange flips one target conditioned on a specified pattern of all $N-1$ other logical bits. Surrounding NOTs convert negative controls, using at most $2(N-1)$ NOTs. For $N\ge 3$, a Toffoli chain computes the conjunction into $N-2$ clean bits, a CNOT flips the target, and the chain is reversed. This uses $2(N-2)$ Toffoli gates and one CNOT. Thus the total is at most $4N-5<4N$, with clean work restored.

For $N=2$, one CNOT, possibly surrounded by two NOTs, suffices. Multiplication by the path bound and number of transpositions proves eq:synthesis.