At \(m=10\), the total-gate accounting points the other way
On this page · Permalink · Source line 474
Here \(n=1,022\). The full function uses 17 Toffolis; its quadratic grade needs 511. However, computing and uncomputing the \(m\) parities also uses
The explicit full construction has \(10,237\) total gates. The quadratic accumulation uses only 511 total gates.
The left panel is a valid nonlinear-cost separation. The right panel prevents interpreting it as an exponential ordinary total-gate separation. The total full construction is \(O(n\log n)\), whereas the quadratic construction is \(n/2\) gates.
A proposed invariant that charges an original computation for every separately extracted grade would have to justify that extraction's cost. These formulas refute an overhead bounded only by a polynomial in the original nonlinear count, independently of input and linear resources. They do not exclude an overhead polynomial in \(n+T\) or a different precisely defined invariant.
Exact counts obtained from the source constructors; optimal Toffoli formulas have written proofs. The full total-gate count is an upper construction count.