Theorem: Exact reversible implementation with retained inputs

Every $f_i$ has a NOT–CNOT–Toffoli realization of

with at most $B$ clean work bits and the conservative gate bound

Five commands can be composed with six $B$-bit snapshot blocks, one $B$-bit work reserve, and at most $5G_B$ gates. The original input snapshots are retained; the work is returned to zero. The circuit acts as identity on internal matter and every untouched reference.

Proof. For each output bit, express its Boolean function as the XOR of its accepting input minterms. Each minterm is a NOT on the target conditioned on one complete $B$-bit pattern. Negative controls use at most $2B$ NOTs. A ladder of at most $B$ clean work bits computes and uncomputes the conjunction with at most $2B$ further Toffoli-type steps, with CNOT or NOT handling the small cases. Thus $4B+2$ gates per minterm is sufficient. There are at most $B{2}^B$ minterms. The resulting transformation is the total permutation $(x,y)\mapsto (x,y\oplus f_i(x))$.

Apply this construction from snapshot $i$ into blank snapshot $i+1$. The six snapshots retain all information needed for a reversal; no many-to-one erasure is asserted. Tensor every gate with identity on matter and reference.