Finite reversible synthesis and its scaling boundary

The local construction uses ordinary reversible compute–copy–uncompute. Cheung's VIII-C includes a different finite-dictionary permutation-completion lemma with an explicit gate count proportional to the dictionary size CheungVIIIC ({lem:completion}). It is a relevant comparison, but it is not the source's dyadic probability completion.

The two uses of the word “completion” have different types:

Neither supplies the other. A dictionary may have $2^{\ell }$ entries even when each entry has only polynomially many bits.