Proposition: Exact finite circuit realization

The permutations $U_A,U_B$ have exact finite NOT–CNOT–Toffoli realizations with clean work returned in $|0⟩$. Code, location, and history wires are returned. The internal matter action is the identity.

Proof. Every finite permutation is a product of transpositions. For two $M$-bit strings choose a nonrepeating Gray path $v_0,\dots ,v_D$. The product

exchanges the endpoints and restores the intermediate strings. For $D=1$, use the single adjacent transposition.

An adjacent transposition is a NOT on the differing bit, controlled on the specified pattern of all other bits. Surrounding NOTs provide negative controls. For two or more controls, compute their conjunction into clean work using Toffoli gates, flip the target, and uncompute. Zero and one control use NOT and CNOT. At most $M$ work bits suffice for this existence construction.

Every gate consumes and returns its interface. Work is uncomputed; transport history is deliberately retained. Tensoring with the identity on internal matter completes the realization.