17.3 Extracting the quadratic grade
On this page · Permalink · Source line 439
Theorem 17.4: Exact cost of the extracted grade
Let \(Q_m=[P_m]_2\) denote the homogeneous quadratic part in the original \(x_v\) coordinates. Then
where every unordered pair is used once, and
Proof
The excluded columns give \(P_m(0)=P_m(e_v)=0\). For distinct \(u,v\), Boolean coefficient inversion therefore gives
The map \(v\mapsto v+a\) is a fixed-point-free involution of \(V\), so the displayed terms form \(n/2\) disjoint pairs. Proposition 17.2 supplies the exact costs.
Counterexample 17.5: Projection does not preserve safe support
The quadratic extraction \([P_m]_2\) need not be supported on the positive set of \(P_m\).
Proof
Take \(m=3\), identify the columns with the integers \(1,\ldots,6\) using their three-bit expansions, and set \(x_1=x_3=x_4=1\) with all other inputs zero. Their column sum is \(1+3+4=6\) under bitwise XOR, not \(a=7\), so \(P_3=0\). Among the complementary pairs \((1,6),(2,5),(3,4)\), exactly \((3,4)\) has both inputs one. Thus \(Q_3=1\). In the source ordering this is the logical assignment encoded by integer 13.
| \(m\) | Actual inputs \(n\) | \({T_{\mathrm{rest}}}(P_m)\) | \({T_{\mathrm{rest}}}(Q_m)\) | Constructed total gates for \(P_m\) |
|---|---|---|---|---|
| 2 | 2 | 1 | 1 | 5 |
| 3 | 6 | 3 | 3 | 21 |
| 4 | 14 | 5 | 7 | 61 |
| 6 | 62 | 9 | 31 | 381 |
| 8 | 254 | 13 | 127 | 2,045 |
| 10 | 1,022 | 17 | 511 | 10,237 |
These are exact cost formulas. The large-input entries were not obtained by searching for optimal circuits. The full construction uses
CNOTs as well as \(2m-3\) Toffolis, giving total count \(O(n\log n)\). The projected quadratic has \(n/2\) total gates.
What the counterexample excludes
The nonlinear projection cost grows exponentially in \(m\), but only linearly in actual input length \(n\). The example does not give an exponential separation in ordinary total gate count. It rules out treating this grade extraction as having overhead bounded only by a polynomial in the original Toffoli count, independently of linear and input-size resources. It also shows that homogeneous extraction may destroy safety. It does not exclude a bound polynomial in \(n+T\) or every possible graded invariant.
The source checks all pair coefficients and exact ranks for \(2\le m\le10\). Full truth tables and complete restored evaluations are restricted to \(m=2,3,4\). At \(m=4\), the quadratic accepts 7,616 inputs that the whole function rejects; that count is finite evidence, distinct from the explicit universal mechanism above.