Proposition: Exact finite reversible circuit

The permutation $U_{\mathrm{ex}}$ has an exact finite NOT–CNOT–Toffoli realization with clean work bits returned to zero. Code, location, and history wires are returned. The matter density operator is acted on by the identity.

Proof. Every finite permutation is a product of transpositions. For two $M$-bit strings, choose a Gray path $v_0,\dots ,v_D$ between them, changing one differing bit at a time. If $s_j=(v_j{v}_{j+1})$, the product

exchanges the endpoints and fixes the intermediate strings.

An adjacent transposition is a target NOT controlled on a specified pattern of the other bits. Negative controls use surrounding NOT gates. A multiple-control NOT is implemented by computing the conjunction of its controls into clean work bits with Toffoli gates, flipping the target, and reversing the conjunction computation. Zero, one, or two controls use NOT, CNOT, or Toffoli directly. At most $M$ clean work bits suffice.

Apply this construction to a transposition decomposition of $U_{\mathrm{ex}}$. Each gate consumes and returns its interface. The work is uncomputed, but the history required by eq:event-code-map is deliberately retained. Tensor the circuit with the identity on matter.