17.2 A compact whole function
On this page · Permalink · Source line 414
Let \(m\ge2\), let \(a=(1,\ldots,1)\in{\mathbb F_2}^m\), and introduce one logical bit \(x_v\) for each
There are \(n=2^m-2\) such bits. Define
Theorem 17.3: Exact nonlinear cost of the whole function
For the family above,
Proof
The linear map \(x\mapsto(L_1(x),\ldots,L_m(x))\) has rank \(m\), since its columns include the standard basis vectors. Extend these forms to an invertible system of linear coordinates. In those coordinates \(P_m\) is the product of the first \(m\) variables, with the other \(n-m\) variables unused.
Degree is invariant under an invertible affine change, so \(\deg P_m=m\) and Lemma 13.2 gives \(M(P_m)\ge m-1\). A product chain attains it.
For the restored lower bound, the safe ideal of the product in these coordinates consists of polynomials divisible by the \(m\)-variable monomial. Any nonzero safe polynomial has degree at least \(m\). Theorem 15.3 gives \(2m-3\). Compute the \(m\) parities onto clean registers by CNOT, apply the optimal monomial oracle there, and uncompute the parities. No additional Toffolis are needed.