Exact nonlinear projection costs versus actual input length
On this page · Permalink · Source line 449
The source proves the all-size formulas
The chart uses actual input length \(n=2^m-2\) on its horizontal axis.
For \(Q_m\), each disjoint quadratic pair is accumulated directly into the target with one Toffoli. The lower bound allows nonlinear intermediates: any computation with \(t\) multiplications is affine on an affine subspace of codimension at most \(t\). A nondegenerate quadratic can be affine only on a subspace with isotropic direction space, whose dimension is at most \(n/2\). Thus \(t\ge n/2\).
The separation grows exponentially in \(m\), but \(n\) itself grows exponentially in \(m\). The quadratic cost is linear in actual input length. The conclusion is about nonlinear generation and a specified grade extraction operation, not a superpolynomial unrestricted circuit bound.
All-size written cost proofs; constructor gate counts freshly asserted through \(m=10\). No full truth-table enumeration at \(m>4\) is claimed.