Proposition: Explicit reversible lookup bound

Given the complete truth table, $O_f$ has an exact reversible implementation using

elementary $H,T,T^{†},\mathrm{CNOT}$ gates and $O(m+1)$ clean scratch qubits. A dense representation of the table has $2^m$ classical bits.

This is an upper bound for a particular construction, not a lower bound for every implementation.

Proof. For each address $a$ with $f(a)=1$, negate the zero positions of $a$, compute the AND of the $m$ address bits into a chain of clean scratch bits, flip the answer conditionally on that AND, and uncompute the chain and negations. Exactly one address predicate is true on each basis input. The result is the required XOR, with all scratch restored. Each predicate uses $O(m+1)$ NOT, CNOT, and Toffoli gates. The cases $m=0,1$ are immediate.

For completeness, NOT is $H{T}^{4}H$. The integer identity

gives an exact controlled-controlled $Z$: compute each displayed parity into clean scratch, apply its $T$ or $T^{†}$ phase, and uncompute. Conjugating its target by $H$ gives Toffoli. Thus each required reversible gate has a constant-size exact implementation in the allowed library.