15.2 The restored lower bound
On this page · Permalink · Source line 177
Theorem 15.3: Affine-optimized complete-cover bound
Every restored implementation of \(f\) with \(T\) Toffoli gates satisfies
In particular,
Proof
Cut the implementation after \(\lfloor T/2\rfloor\) Toffolis. The forward prefix and the inverse suffix use at most \(\lceil T/2\rceil\) Toffolis each. By Lemma 13.2, each of their coordinates, and therefore each discrepancy \(H_i\), has degree at most
Theorem 14.1 gives \(H_i\le f\) and a complete cover of the positive inputs. Every positive \(v\) is therefore detected by a safe polynomial within this degree bound, so
Integer rounding gives \(T\ge2\beta(f)-3\).
At the end of a restored oracle the logical inputs are available unchanged. CNOTs from those inputs and, when needed, a target NOT append any affine \(\ell\) to the target at no Toffoli cost. Apply the same inequality to each \(f+\ell\) and maximize. Finally, reading the target with initial value zero computes \(f\) using \(T\) multiplications, so Lemma 13.2 gives \(T\ge\deg f-1\).
Scope of the lower bound
The circuit may use output feedback and arbitrary dirty intermediate states, but it must satisfy the restored classical oracle convention. The inequality does not apply automatically to a model with discarded garbage or measurement. Because \(\beta^*(f)\le n\), this parameter alone cannot prove a superpolynomial lower bound in the actual input length.