Quantum and Circuits

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{Scope, notation, and computational model}
2 \label{c:ch:foundations}
3 \section{Boolean and algebraic conventions}
4 A Boolean function is a map $f:\B^n\to\B$. Unless a different field is explicitly stated, polynomials are the unique multilinear representatives in
5 \[
6 \mathcal R_n=\F[x_1,\ldots,x_n]/(x_i^2-x_i:1\le i\le n).
7 \]
8 Addition in this ring is XOR. Multiplication is AND. Boolean OR is written $\lor$ and satisfies $a\lor b=a+b+ab$. A statement $h\le f$ is pointwise and means that $h$ has no positive value at a negative input of $f$.
9 
10 The degree of a nonzero function is its multilinear algebraic degree. A nonzero constant has degree zero. For mathematical statements involving a constant-zero function we use $\deg0=-\infty$; stored profile tables and Python helpers use their documented sentinels instead. Those implementation conventions do not change the inequalities.
11 
12 For $S\subseteq[n]$, write $x^S=\prod_{i\in S}x_i$ and let $1_S$ be the input with support $S$. A minterm of a monotone function means an inclusion-minimal positive support, not an arbitrary positive input.
13 
14 \begin{longtable}{@{}>{\RaggedRight\arraybackslash}p{1.1in}>{\RaggedRight\arraybackslash}p{5.0in}@{}}
15 \toprule
16 \textbf{Symbol} & \textbf{Meaning}\\\midrule\endhead
17 $C(f)$ & Minimum fan-in-two AND/OR/NOT gate count, allowing fan-out.\\
18 $L(f)$ & Minimum total NOT/CNOT/Toffoli count of a restored implementation.\\
19 $T$ & Number of Toffoli gates in a specified implementation.\\
20 $\KTrest(f)$ & Minimum such Toffoli count, allowing any finite zero workspace.\\
21 $M(f)$ & Minimum AND count in an XOR--AND computation, with affine operations uncharged.\\
22 $I_f$ & Boolean functions supported only on positive inputs of $f$.\\
23 $\alpha_1(f)$ & Minimum degree of one nonzero member of $I_f$.\\
24 $\beta_v(f)$ & Minimum degree of a member of $I_f$ that is one at $v$.\\
25 $\beta(f),\beta^*(f)$ & Complete-cover degree and its affine-output optimization.\\
26 $[P]_2$ & Homogeneous degree-two component of the multilinear polynomial $P$ in the specified coordinates.\\
27 \bottomrule
28 \end{longtable}
29 
30 \section{The restored classical oracle}
31 A legal NOT changes one target bit. A CNOT adds a control bit to a distinct target. A Toffoli adds the product of two distinct controls to a third distinct wire. Gates have positive controls and are self-inverse. Their composition is a permutation of all register states.
32 
33 A restored oracle is a circuit satisfying
34 \begin{equation}\label{c:eq:oracle}
35 (x,0^a,y)\longmapsto(x,0^a,y+f(x))
36 \end{equation}
37 for every logical input $x$ and both initial target values $y\in\B$. The zero-workspace condition is imposed at the boundary, not at intermediate times. The circuit may disturb logical inputs, use output feedback, reuse intermediate values, and make arbitrary reversible excursions before restoring the required registers.
38 
39 NOT and CNOT are free only when counting $T$. They are charged in $L$. This distinction is essential in the projection example. There are no measurements, quantum phases, discarded work registers, or unverified ancilla initializations in this model.
40 
41 \section{Comparison with ordinary circuits}
42 \begin{theorem}[Classical/restored simulation comparison]\label{c:thm:simulation}
43 For every Boolean function $f$,
44 \[
45 \frac{C(f)}5\le L(f)\le6C(f)+1.
46 \]
47 \end{theorem}
48 \begin{proof}
49 Compute every Boolean gate onto a fresh zero wire. An AND costs one Toffoli. A NOT of an existing signal is obtained with one NOT and one CNOT. An OR is computed as $a+b+ab$, using two CNOTs and one Toffoli. Repeated operands are simplified to a copy, not encoded as an illegal repeated-control gate. Compute the output, copy it to $y$, and reverse the first computation. This uses at most $6C(f)+1$ gates and restores every work register.
50 
51 Conversely, express each reversible gate as an ordinary Boolean update. XOR has a four-gate AND/OR/NOT realization. A Toffoli needs that XOR plus one AND, hence at most five gates. Substitute zero for initial ancillas and $y=0$, then read the final target. The resulting Boolean circuit has at most $5L(f)$ gates.
52 \end{proof}
53 
54 \section{The degree bound used throughout}
55 \begin{lemma}[Degree per multiplication]\label{c:lem:degree}
56 An XOR--AND computation with $t$ AND gates has output degree at most $t+1$, allowing constants and arbitrary sharing. The same bound holds for each coordinate of a reversible computation containing $t$ Toffoli gates.
57 \end{lemma}
58 \begin{proof}
59 Introduce a formal Boolean variable for each AND output. Its defining expression is a product of two affine forms in the logical inputs and earlier gate variables. The final output is affine in the inputs and all gate variables.
60 
61 Substitute the gate variables in reverse topological order. A multilinear monomial contains the variable being replaced at most once. Replacing it by a quadratic expression raises degree by at most one; multilinear reduction cannot raise it. After $t$ substitutions the degree is at most $t+1$.
62 
63 A Toffoli contributes one multiplication to such a straight-line computation, while NOT and CNOT are affine. The argument also applies to a suffix executed backwards because the gates are self-inverse.
64 \end{proof}
65 The source identifies this standard degree bound with the XOR--AND background in \cite{c:soeken}.
66 
67 
68 \section{A degree invariant that retains sharing}
69 The preceding Boolean substitution proof applies to general XOR--AND straight-line computations. The later formal development proves the classical reversible specialization directly on the evolving register state. This route makes the resource accounting visible without unfolding reused registers into duplicated formulas.
70 
71 \begin{theorem}[Register-product degree invariant]\label{c:thm:register-products}
72 Let $s_i(x)$ be the contents of a finite register after $t$ Toffoli gates, with arbitrary intervening NOT and CNOT gates. Initial register contents are affine functions of $x$. For every finite list $L$ of $r$ register indices, including repeated indices,
73 \[
74  \deg\left(\prod_{i\in L}s_i(x)\right)\le t+r.
75 \]
76 The zero-function convention is as above. In the formal source the conclusion is the concrete representation certificate \texttt{DegreeLE}.
77 \end{theorem}
78 \begin{proof}
79 Initially a product of $r$ affine functions has degree at most $r$. Suppose a gate toggles register $u$ by a product of $q$ controls, with $q=0,1,2$ for NOT, CNOT, and Toffoli respectively. If $u$ does not occur in $L$, the product is unchanged. If it occurs, Boolean idempotence removes all its repetitions. Let $R$ be the remaining list, so $|R|+1\le r$. The updated product is
80 \[
81  s_u\prod_{i\in R}s_i+
82  \left(\prod_{j\in\mathrm{controls}}s_j\right)\prod_{i\in R}s_i.
83 \]
84 By the old invariant, these two summands have degrees at most $t+1+|R|$ and $t+q+|R|$. The latter is at most $t+r+\max\{q-1,0\}$. NOT and CNOT therefore consume no degree budget; a Toffoli consumes at most one. Induction along the actual gate list proves the claim. The empty list is the constant-one product and is also covered.
85 \end{proof}
86 For $r=1$ this recovers the coordinate bound. The initial target can be fixed to either boundary bit while the inputs vary. Temporary input disturbance, dirty intermediate workspace, output controls, and repeated use of earlier products are all allowed. The formal locators are \texttt{workspaceDegree\_run} and \texttt{canonical\_run\_coordinate\_degree}.
87 
88 \begin{circuitscopebox}{The representation is part of the theorem}
89 \texttt{DegreeLE(d,f)} is tied by proved equivalences to an explicit finite XOR of monomials with length at most $d$. It is not an assumed degree oracle. Canonical algebraic-normal-form extraction and a separate generic XOR--AND simulation compiler are outside this formal block.
90 \end{circuitscopebox}
91 
92 \chapter{Exact cut comparison and safe discrepancies}
93 \label{c:ch:cut}\claim{C01}
94 \begin{theorem}[Cut-comparison identity and complete coverage]\label{c:thm:cut}
95 Let a restored oracle be written $\mathcal C=Q\circ P$, and put $R=Q^{-1}$. Suppress zero ancillas in boundary arguments and define
96 \[
97  A(x)=P(x,0),\qquad B(x)=R(x,0),\qquad
98  D(x)=P(x,1)+P(x,0).
99 \]
100 These are vectors indexed by all registers. Then
101 \begin{equation}\label{c:eq:cut}
102  A(x)+B(x)=f(x)D(x),\qquad D(x)\ne0.
103 \end{equation}
104 Consequently, the coordinate discrepancies $H_i=A_i+B_i$ satisfy
105 \begin{equation}\label{c:eq:cover}
106  H_i\le f\quad\hbox{for every }i,\qquad
107  \bigvee_iH_i=f.
108 \end{equation}
109 \end{theorem}
110 \begin{proof}
111 For a boundary state with target $z$, correctness of the full circuit gives
112 \[
113  R(x,z)=P(x,z+f(x)).
114 \]
115 When $f(x)=0$, this says $B(x)=A(x)$. When $f(x)=1$, it says $B(x)=P(x,1)$, and the discrepancy is $D(x)$. Both cases are summarized by \eqref{c:eq:cut}.
116 
117 The prefix $P$ is a permutation. Its images of the two distinct boundary states $(x,0)$ and $(x,1)$ are different, so $D(x)$ is a nonzero vector.
118 
119 If $f(x)=0$, every discrepancy is zero. If $f(x)=1$, at least one discrepancy is one. These are precisely the safety and complete-coverage assertions in \eqref{c:eq:cover}.
120 \end{proof}
121 
122 \section{What the comparison does and does not require}
123 The suffix need not reverse the prefix. Output feedback and a target direction distributed among many registers are permitted. Only boundary correctness and reversibility are used. Equivalently,
124 \[
125  f(x)=1\quad\Longleftrightarrow\quad P(x,0)\ne Q^{-1}(x,0).
126 \]
127 This is a necessary representation, not a circuit lower bound from packet count. Expanded monomial counts, individual degrees, and algebra dimensions remain distinct from the shared cost of constructing the complete family. The declared finite cut checks are reported in Section~\ref{c:app:evidence}.
128 
129 \chapter{Complete safe-packet degree}
130 \label{c:ch:degree}\claim{C02}
131 \section{Pointwise coverage rather than one easy packet}
132 Let
133 \[
134  I_f=\{h\in\mathcal R_n:h(1+f)=0\}.
135 \]
136 This is the ideal of functions supported only on the accepting set of $f$. For nonzero $f$, the one-packet parameter is
137 \[
138  \alpha_1(f)=\min\{\deg h:0\ne h\in I_f\}.
139 \]
140 It asks for one safe nonzero polynomial, which may detect only an easy portion of the accepting set. One-sided polynomial immunity is established terminology in this setting; see the background reference \cite{c:beckli}.
141 
142 For a positive input $v$, define instead
143 \[
144  \beta_v(f)=\min\{\deg h:h\in I_f,\ h(v)=1\},\qquad
145  \beta(f)=\max_{v:f(v)=1}\beta_v(f).
146 \]
147 Set $\beta(0)=0$. Thus $\beta(f)$ is the degree needed before safe polynomials collectively detect \emph{every} positive input. Finally, put
148 \[
149  \beta^*(f)=\max_{\ell\in\Aff_n}\beta(f+\ell),
150 \]
151 where $\Aff_n$ is the set of affine Boolean functions on the logical inputs.
152 
153 \begin{proposition}[Basic size bounds]\label{c:prop:beta-bounds}
154 For nonzero $f$ on $n$ inputs,
155 \[
156  \alpha_1(f)\le\beta(f)\le n.
157 \]
158 If $f$ has at least two positive inputs, then $\beta(f)\le n-1$. In particular $\beta^*(f)\le n$.
159 \end{proposition}
160 \begin{proof}
161 Any polynomial detecting a specified positive input is nonzero, giving the first inequality. For $v\in\B^n$, its point indicator is
162 \[
163  \delta_v(x)=\prod_{i:v_i=1}x_i\prod_{i:v_i=0}(1+x_i).
164 \]
165 If $f(v)=1$, then $\delta_v\in I_f$ and has degree $n$, proving the upper bound.
166 
167 If $v$ and $w$ are distinct positive inputs, $\delta_v+\delta_w$ is safe and equals one at $v$. The degree-$n$ coefficients of its two summands are both one, so they cancel. Its degree is at most $n-1$. Do this for each positive $v$. The last assertion applies the general bound to every affine adjustment, with the stated zero convention.
168 \end{proof}
169 
170 \begin{proposition}[Affine input invariance]\label{c:prop:affine-invariance}
171 Invertible affine changes of logical input coordinates preserve $\alpha_1$, $\beta$, and $\beta^*$, with the pointwise parameters transported by the corresponding bijection of inputs.
172 \end{proposition}
173 \begin{proof}
174 Composition with an affine map cannot increase multilinear degree. Composition with its affine inverse proves equality of degrees. Such composition bijects the accepting and rejecting inputs, hence maps safe polynomials bijectively to safe polynomials and preserves their pointwise detecting property. It also permutes the affine output masks used in the definition of $\beta^*$.
175 \end{proof}
176 
177 \section{The restored lower bound}
178 \begin{theorem}[Affine-optimized complete-cover bound]\label{c:thm:complete-bound}
179 Every restored implementation of $f$ with $T$ Toffoli gates satisfies
180 \begin{equation}\label{c:eq:complete-bound}
181  T\ge\max\{0,\ \deg f-1,\ 2\beta^*(f)-3\}.
182 \end{equation}
183 In particular,
184 \[
185  T\ge\max\{0,\ \deg f-1,\ 2\beta(f)-3,\ 2\beta(1+f)-3\}.
186 \]
187 \end{theorem}
188 \begin{proof}
189 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~\ref{c:lem:degree}, each of their coordinates, and therefore each discrepancy $H_i$, has degree at most
190 \[
191  \left\lceil\frac T2\right\rceil+1.
192 \]
193 Theorem~\ref{c:thm:cut} 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
194 \[
195  \beta(f)\le\left\lceil\frac T2\right\rceil+1.
196 \]
197 Integer rounding gives $T\ge2\beta(f)-3$.
198 
199 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~\ref{c:lem:degree} gives $T\ge\deg f-1$.
200 \end{proof}
201 
202 \begin{circuitscopebox}{Scope of the lower bound}
203 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.
204 \end{circuitscopebox}
205 
206 \section{Exact evaluation-span certificates}
207 For an integer $d\ge0$, form the evaluation vector
208 \[
209  v_d(x)=\bigl(x^S\bigr)_{S\subseteq[n],\ |S|\le d},
210 \]
211 and write $U=f^{-1}(0)$.
212 
213 \begin{theorem}[Dual certificate for failure of safe detection]\label{c:thm:dual}
214 For every positive input $v$,
215 \begin{equation}\label{c:eq:dual}
216  \beta_v(f)>d
217  \quad\Longleftrightarrow\quad
218  v_d(v)\in\Span_{\F}\{v_d(u):u\in U\}.
219 \end{equation}
220 \end{theorem}
221 \begin{proof}
222 A degree-at-most-$d$ polynomial is a coefficient covector on the evaluation space. It is safe exactly when it annihilates every negative evaluation vector, equivalently their span. Such a covector can equal one on $v_d(v)$ exactly when $v_d(v)$ lies outside that span. This is finite-dimensional linear duality over $\F$.
223 \end{proof}
224 
225 \begin{corollary}[Finite support of a dual witness]\label{c:cor:dual-witness}
226 When the right side of \eqref{c:eq:dual} holds, there is $W\subseteq U$ with
227 \[
228  v_d(v)=\sum_{u\in W}v_d(u),\qquad
229  |W|\le\sum_{j=0}^{\min(d,n)}\binom nj.
230 \]
231 The cardinality $|W|$ is odd.
232 \end{corollary}
233 \begin{proof}
234 Choose a basis of the span from negative evaluation vectors and express $v_d(v)$ in that basis. Over $\F$, the nonzero coefficients select a subset $W$ of size at most the ambient dimension. The constant-monomial coordinate of every evaluation vector is one; comparing it on both sides shows that $|W|$ is odd.
235 \end{proof}
236 Such a relation is replayable by exact linear arithmetic. It does not provide an efficient way to enumerate all negatives of an arbitrary SAT verifier. The theorem assumes that the negative vectors or their proved structure are available.
237 
238 \section{Monotone specialization}
239 \begin{theorem}[Safe monomial ideal for a monotone function]\label{c:thm:monotone}
240 If $f$ is monotone, $I_f$ has a monomial basis indexed by the positive supports of $f$. For each positive $v$,
241 \[
242  \beta_v(f)=\min\{|S|: S\subseteq\supp(v),\ f(1_S)=1\}.
243 \]
244 Consequently, for nonzero $f$,
245 \[
246  \alpha_1(f)=\text{minimum minterm size},\qquad
247  \beta(f)=\text{maximum minterm size}.
248 \]
249 \end{theorem}
250 \begin{proof}
251 For any Boolean polynomial $h$, its coefficient on $x^S$ is
252 \[
253  [x^S]h=\sum_{T\subseteq S}h(1_T)
254 \]
255 over $\F$. If $S$ is negative for monotone $f$, every subset $T$ is negative. A safe $h$ vanishes at each $1_T$, so its $x^S$ coefficient is zero. Conversely, a monomial on a positive support is safe by monotonicity. This proves the basis assertion.
256 
257 If a safe $h$ satisfies $h(v)=1$, at least one of its nonzero monomials is supported inside $\supp(v)$. That support is positive and has size at most $\deg h$. Conversely, a smallest such positive-support monomial detects $v$. This proves the pointwise formula. Taking the appropriate minima and maxima gives the minterm statements: a minimal positive support cannot contain a smaller positive one, and every positive input contains a minterm.
258 \end{proof}
259 
260 \begin{corollary}[Exact monomial oracle cost]\label{c:cor:monomial}
261 For $k\ge2$,
262 \[
263  \KTrest(x_1x_2\cdots x_k)=2k-3.
264 \]
265 \end{corollary}
266 \begin{proof}
267 The unique positive input of the $k$-variable monomial needs a safe polynomial of degree $k$. The complete-cover lower bound gives $2k-3$. For the matching construction, successively compute $x_1x_2$, then $x_1x_2x_3$, and so on up to a $(k-1)$-fold product on clean work wires. Toggle the output using that product and $x_k$, then uncompute the $k-2$ work products. The count is $(k-2)+1+(k-2)=2k-3$. For $k=2$, a single Toffoli suffices.
268 \end{proof}
269 
270 \chapter{Calibration families and exact small oracles}
271 \label{c:ch:calibration}\claim{C03 and C04}
272 \section{An unbalanced disjunction}
273 For $k\ge2$ and $n=k+2$, define
274 \[
275  B=z_1\cdots z_k,\qquad
276  F_k(a,b,z)=(ab)\lor B=ab+B+abB,\qquad G_k=F_k+a.
277 \]
278 This is a deliberately easy family with two differently sized accepting regions. It separates the cost of finding one safe packet from the degree needed for complete coverage.
279 
280 \begin{proposition}[Raw calibration parameters]\label{c:prop:raw-family}
281 For this family,
282 \[
283  \alpha_1(F_k)=2,\qquad\beta(F_k)=k,\qquad\deg F_k=k+2.
284 \]
285 \end{proposition}
286 \begin{proof}
287 The minterms have supports $\{a,b\}$ and $\{z_1,\ldots,z_k\}$. The first two assertions follow from Theorem~\ref{c:thm:monotone}. The monomial $abB$ has degree $k+2$ and does not cancel with either lower-degree term in the displayed polynomial.
288 \end{proof}
289 
290 \begin{theorem}[Affine optimization of the one-packet parameter]\label{c:thm:family-alpha}
291 For every $k\ge2$,
292 \[
293  \max_{\ell\in\Aff_n}\alpha_1(F_k+\ell)=3.
294 \]
295 \end{theorem}
296 \begin{proof}
297 First restrict to the face $z_1=0$. There $F_k+\ell$ becomes $ab+\ell|_{z_1=0}$, a nonzero quadratic. If the restricted affine term contains a remaining $z$ variable, set $a=0$ and set the remaining affine form to one. This gives an accepting affine subspace of codimension at most two inside the face. If it contains no remaining $z$ variable, fix $a,b$ to an accepting pair instead. The indicator of the resulting affine subspace in the full input space has degree at most three and is safe. Thus every affine adjustment has a nonzero safe polynomial of degree at most three.
298 
299 For equality, take $\ell=a$. The degree-three polynomial
300 \[
301  a(1+b)(1+z_1)
302 \]
303 is safe for $G_k$. Suppose a safe $h$ of degree at most two existed. On $a=0$, acceptance requires $B=1$. For $k\ge3$, the monotone-ideal argument forces $h|_{a=0}=0$, hence $h=aL$ with $L$ affine in the remaining variables. The negative face $a=b=1$ forces $L(1,z)=0$, so $L=c(1+b)$. The negative point $a=1,b=0,z=(1,\ldots,1)$ then forces $c=0$.
304 
305 When $k=2$, the restriction can initially be $h|_{a=0}=cB$. Write $h=cB+aL$. On the same negative face $a=b=1$, the quadratic term $cB$ cannot be cancelled by affine $L$, so $c=0$. The previous argument then applies. There is no nonzero safe polynomial of degree at most two, proving equality.
306 \end{proof}
307 
308 \begin{theorem}[Affine optimization of complete coverage]\label{c:thm:family-beta}
309 For every $k\ge2$,
310 \[
311  \beta^*(F_k)=k+1.
312 \]
313 \end{theorem}
314 \begin{proof}
315 Restrict $G_k=F_k+a$ to $b=1$. Then
316 \[
317  G_k|_{b=1}=(1+a)B.
318 \]
319 This is the indicator of one point on $k+1$ variables. At the positive input $a=0,b=1,z=(1,\ldots,1)$, a safe detecting polynomial must restrict to that singleton indicator and therefore have degree at least $k+1$. Thus $\beta(G_k)\ge k+1$.
320 
321 For the upper bound, Theorem~\ref{c:thm:family-alpha} shows that no $F_k+\ell$ is a singleton indicator: a singleton would have one-packet degree $n=k+2>3$. These functions are also nonzero because $F_k$ is not affine. Each has at least two positive inputs, so Proposition~\ref{c:prop:beta-bounds} gives $\beta(F_k+\ell)\le n-1=k+1$.
322 \end{proof}
323 
324 \begin{corollary}[Restored cost interval for the calibration family]\label{c:cor:family-cost}
325 For $n=k+2$,
326 \[
327  2n-5\le\KTrest(F_k)\le2n-3.
328 \]
329 \end{corollary}
330 \begin{proof}
331 The lower bound follows from Theorems~\ref{c:thm:complete-bound} and \ref{c:thm:family-beta}. For the upper bound, compute $A=ab$ with one multiplication and $B$ using $k-1$ multiplications. Toggle the output by $A+B+AB$, requiring one output Toffoli and affine additions. Uncompute $A$ and $B$. The total Toffoli count is $k+1+k=2k+1=2n-3$.
332 \end{proof}
333 
334 The preceding combined bound $\max\{0,\deg F_k-1,2\max_{\ell}\alpha_1(F_k+\ell)-3\}$ gives $n-1$ for this family; its immunity-only term is the constant $3$. The complete-cover bound gives $2n-5$. The stronger estimate can also be recognized by restriction to $b=1$ followed by a free affine output adjustment. No exact optimum is claimed when the displayed endpoints differ.
335 
336 \begin{center}
337 \begin{tabular}{@{}rrrrr@{}}
338 \toprule
339 Inputs $n$ & $\max_\ell\alpha_1$ & $\beta^*$ & One-packet bound & Complete-cover bound\\\midrule
340 4 & 3 & 3 & 3 & 3\\
341 5 & 3 & 4 & 4 & 5\\
342 6 & 3 & 5 & 5 & 7\\
343 7 & 3 & 6 & 6 & 9\\
344 8 & 3 & 7 & 7 & 11\\
345 9 & 3 & 8 & 8 & 13\\
346 \bottomrule
347 \end{tabular}
348 \end{center}
349 The formulas are proved for all $k\ge2$. The source evaluates the designated family truth tables through nine inputs, but checks every affine mask only through eight. The ninth-input affine maximum is justified by the proof, not by a stored exhaustive mask search.
350 
351 \section{An explicit moment certificate}
352 On the face $b=1$, every point except $v=(a=0,z=(1,\ldots,1))$ is negative for $G_k$. A polynomial of degree at most $k$ sums to zero over the $(k+1)$-dimensional cube: each monomial omits some coordinate and contributes an even number of ones. Therefore
353 \[
354  v_k(v)=\sum_{u\ne v\text{ on the face}}v_k(u).
355 \]
356 This is the certificate from Theorem~\ref{c:thm:dual}, proving that no safe degree-$k$ polynomial detects $v$.
357 
358 The finite four-input computation found $\max_\ell\alpha_1(f+\ell)=\beta^*(f)$ for every function in that domain. The family above disproves extrapolation of that equality: it already fails at five inputs, with values three and four, and the difference grows without bound.
359 
360 \section{All functions on at most three inputs}
361 \begin{theorem}[Exact small restored-oracle calibration]\label{c:thm:small-oracles}
362 For every Boolean function on one, two, or three logical inputs, the bound in Theorem~\ref{c:thm:complete-bound} is attained by an explicit restored implementation. The optimum Toffoli counts are zero for affine functions, one for nonaffine quadratics, and three for three-input cubics.
363 \end{theorem}
364 \begin{proof}
365 An affine function is added to the target using only NOT and CNOT gates, so its optimum is zero.
366 
367 A nonaffine quadratic on at most three variables has an alternating polar matrix of rank two. In suitable invertible linear coordinates, its quadratic part is a product of two linear forms; the remaining part is affine. A single Toffoli, together with affine preparation and restoration, computes the oracle. The degree bound requires at least one.
368 
369 A cubic on three variables has the form
370 \[
371  x_1x_2x_3+q(x)+\ell(x),
372 \]
373 with $q$ quadratic and $\ell$ affine. Translating $x_i\mapsto x_i+c_i$ adjusts independently the coefficients of $x_jx_k$, so all quadratic terms can be cancelled. The resulting function is a three-variable monomial plus an affine function. Affine input changes and affine output additions cost no Toffolis. Corollary~\ref{c:cor:monomial} gives both the lower bound three and a matching restored construction.
374 \end{proof}
375 
376 There are $4+16+256=276$ functions over the three input sizes. The distribution is
377 \[
378  \begin{array}{c|rrr}
379  \text{Optimum Toffolis}&0&1&3\\\hline
380  \text{Number of functions}&28&120&128.
381  \end{array}
382 \]
383 The source constructs and checks the actual circuits. Optimality is obtained from the written lower bounds and matching constructions, not from exhaustive enumeration of all reversible circuits.
384 
385 \chapter{Homogeneous projection: cost and safety}
386 \label{c:ch:projection}\claim{C05}
387 This chapter separates the nonlinear cost of a complete function from the nonlinear cost of one extracted homogeneous component. It also shows that an algebraic projection need not preserve safe support.
388 
389 \section{Two supporting lower bounds}
390 \begin{lemma}[Affine subspace after multiplication restrictions]\label{c:lem:affine-subspace}
391 If a Boolean function on $n$ inputs is computed with $t$ AND gates in an XOR--AND circuit, there is an affine subspace of dimension at least $n-t$ on which the output is affine.
392 \end{lemma}
393 \begin{proof}
394 Process the AND gates in topological order while maintaining an affine subspace on which all preceding product outputs are affine. The operands of the next gate are then affine on the current subspace. If an operand is constant, their product is already affine. Otherwise impose one nonempty affine equation setting that operand to zero. This loses at most one dimension and makes the product affine. Earlier affine outputs stay affine under restriction. After at most $t$ restrictions the output is affine on a subspace of dimension at least $n-t$.
395 \end{proof}
396 This is the affine-restriction method used in the background literature on multiplicative complexity \cite{c:findboyar}. The proof is reproduced here in the scalar convention needed below.
397 
398 \begin{proposition}[Exact cost of a nondegenerate paired quadratic]\label{c:prop:quadratic-cost}
399 For even $n$, let
400 \[
401  Q(x)=x_1x_2+x_3x_4+\cdots+x_{n-1}x_n.
402 \]
403 Then
404 \[
405  M(Q)=\KTrest(Q)=n/2.
406 \]
407 \end{proposition}
408 \begin{proof}
409 The polar bilinear form of $Q$ is the full-rank alternating form made of $n/2$ disjoint $2\times2$ blocks. If $Q$ is affine on an affine subspace with direction space $U$, its second differences vanish on $U$, so $U$ is totally isotropic. Nondegeneracy gives $\dim U\le n/2$.
410 
411 Lemma~\ref{c:lem:affine-subspace} therefore implies $n-t\le n/2$, or $t\ge n/2$, for any XOR--AND computation. Every restored Toffoli implementation gives such a computation by fixing its ancillary inputs and initial target, so the same lower bound applies to $\KTrest$. Directly add the $n/2$ disjoint pair products to the target with one Toffoli each. This attains both bounds and requires no nonlinear work register.
412 \end{proof}
413 
414 \section{A compact whole function}
415 Let $m\ge2$, let $a=(1,\ldots,1)\in\F^m$, and introduce one logical bit $x_v$ for each
416 \[
417  v\in V=\F^m\setminus\{0,a\}.
418 \]
419 There are $n=2^m-2$ such bits. Define
420 \[
421  L_j(x)=\sum_{v:v_j=1}x_v,\qquad
422  P_m(x)=\prod_{j=1}^mL_j(x).
423 \]
424 
425 \begin{theorem}[Exact nonlinear cost of the whole function]\label{c:thm:whole-cost}
426 For the family above,
427 \[
428  M(P_m)=m-1,\qquad\KTrest(P_m)=2m-3.
429 \]
430 \end{theorem}
431 \begin{proof}
432 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.
433 
434 Degree is invariant under an invertible affine change, so $\deg P_m=m$ and Lemma~\ref{c:lem:degree} gives $M(P_m)\ge m-1$. A product chain attains it.
435 
436 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~\ref{c:thm:complete-bound} 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.
437 \end{proof}
438 
439 \section{Extracting the quadratic grade}
440 \begin{theorem}[Exact cost of the extracted grade]\label{c:thm:grade-cost}
441 Let $Q_m=[P_m]_2$ denote the homogeneous quadratic part in the original $x_v$ coordinates. Then
442 \[
443  Q_m=\sum_{\{v,v+a\}\subseteq V}x_vx_{v+a},
444 \]
445 where every unordered pair is used once, and
446 \[
447  M(Q_m)=\KTrest(Q_m)=n/2=2^{m-1}-1.
448 \]
449 \end{theorem}
450 \begin{proof}
451 The excluded columns give $P_m(0)=P_m(e_v)=0$. For distinct $u,v$, Boolean coefficient inversion therefore gives
452 \[
453  [x_ux_v]P_m=P_m(e_u+e_v)=[u+v=a].
454 \]
455 The map $v\mapsto v+a$ is a fixed-point-free involution of $V$, so the displayed terms form $n/2$ disjoint pairs. Proposition~\ref{c:prop:quadratic-cost} supplies the exact costs.
456 \end{proof}
457 
458 \begin{counterexample}[Projection does not preserve safe support]\label{c:ce:unsafe}
459 The quadratic extraction $[P_m]_2$ need not be supported on the positive set of $P_m$.
460 \end{counterexample}
461 \begin{proof}
462 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.
463 \end{proof}
464 
465 \begin{center}
466 \begin{tabular}{@{}rrrrr@{}}
467 \toprule
468 $m$ & Actual inputs $n$ & $\KTrest(P_m)$ & $\KTrest(Q_m)$ & Constructed total gates for $P_m$\\\midrule
469 2 & 2 & 1 & 1 & 5\\
470 3 & 6 & 3 & 3 & 21\\
471 4 & 14 & 5 & 7 & 61\\
472 6 & 62 & 9 & 31 & 381\\
473 8 & 254 & 13 & 127 & 2,045\\
474 10 & 1,022 & 17 & 511 & 10,237\\
475 \bottomrule
476 \end{tabular}
477 \end{center}
478 These are exact cost formulas. The large-input entries were not obtained by searching for optimal circuits. The full construction uses
479 \[
480  2m(2^{m-1}-1)
481 \]
482 CNOTs as well as $2m-3$ Toffolis, giving total count $O(n\log n)$. The projected quadratic has $n/2$ total gates.
483 
484 \begin{circuitscopebox}{What the counterexample excludes}
485 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.
486 \end{circuitscopebox}
487 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.
488 
489 \chapter{Faithful linear gluing algebras}
490 \label{c:ch:gluing}\claim{C06}
491 This chapter states an exponential dimension result for a specified summary model. The qualifications are part of the theorem's meaning: a lower bound on an algebra's dimension is not automatically a lower bound on the length of a circuit describing one of its elements.
492 
493 \section{The witness algebra}
494 Let $K$ be a field and let $W=\B^m$. The full witness algebra is
495 \[
496  \mathcal B=K^W,
497 \]
498 with pointwise addition and multiplication. For each witness $v$, let $\delta_v$ be its indicator function. These form a basis of $\mathcal B$ and satisfy
499 \[
500  \delta_v^2=\delta_v,\qquad
501  \delta_v\delta_u=0\quad(u\ne v),\qquad
502  \sum_{v\in W}\delta_v=1.
503 \]
504 In characteristic two, this is equivalently the Boolean quotient algebra
505 \[
506  K[w_1,\ldots,w_m]/(w_i^2-w_i:1\le i\le m).
507 \]
508 
509 \begin{theorem}[Dimension of a faithful multiplicative summary]\label{c:thm:gluing-dim}
510 Let $\Phi:\mathcal B\to A$ be a $K$-linear multiplicative map into a $K$-algebra. Suppose
511 \[
512  \Phi(\delta_v)\ne0\qquad\text{for every }v\in W.
513 \]
514 Then
515 \[
516  \dim_K A\ge2^m.
517 \]
518 No unital hypothesis on $\Phi$ is required.
519 \end{theorem}
520 \begin{proof}
521 Write $e_v=\Phi(\delta_v)$. Multiplicativity makes these nonzero orthogonal idempotents. If
522 \[
523  \sum_{v\in W}c_ve_v=0,
524 \]
525 multiply the equality by $e_u$. Orthogonality annihilates every term except $c_ue_u$, which must be zero. Since $K$ is a field and $e_u\ne0$, $c_u=0$. This holds for every $u$, so the $2^m$ vectors $e_v$ are linearly independent.
526 \end{proof}
527 
528 \begin{corollary}[Scalar unital summaries are evaluations]\label{c:cor:scalar-eval}
529 Every unital $K$-linear multiplicative map $\Phi:K^W\to K$ is evaluation at exactly one witness.
530 \end{corollary}
531 \begin{proof}
532 An idempotent scalar in a field is either zero or one. Orthogonality allows at most one $\Phi(\delta_v)$ to be one, and preservation of the unit requires exactly one. If it occurs at $v_0$, linearity gives
533 \[
534  \Phi(g)=\Phi\left(\sum_v g(v)\delta_v\right)=g(v_0).
535 \]
536 \end{proof}
537 For $m\ge1$, such a scalar summary loses at least one singleton witness other than $v_0$. At $m=0$, the unique empty witness is preserved by the identity map. The dimension theorem is an elementary product-algebra fact, not a claim of new algebra or a universal computational lower bound.
538 
539 \section{The quantified model boundary}
540 The same map $\Phi$ here serves \emph{all} predicates on a fixed witness space. It is linear, multiplicative, and retains every primitive witness indicator. Under exactly these assumptions, a polynomial-dimensional summary is impossible as $m$ grows.
541 
542 An arbitrary algorithm is not required to satisfy these hypotheses. It may use nonlinear encodings, syntax-dependent operations, changing spaces, or succinct descriptions inside an exponentially large algebra. A description of the algebra and a description of one relevant element can be much shorter than a full coordinate listing.
543 
544 \begin{circuitscopebox}{No dimension-to-circuit inference}
545 The theorem excludes a fixed faithful linear multiplicative compression of the full witness algebra into fewer than $2^m$ dimensions. It does not exclude every polynomial-time decision procedure, does not prove $P\ne NP$, and does not justify treating the algebra's dimension as the circuit cost of an individual decision function.
546 \end{circuitscopebox}
547 
548 The finite scalar controls enumerate 256 linear maps from a two-point witness algebra to $\mathrm{GF}(16)$, 65,536 maps for four points, and 256 maps from an eight-point algebra to $\F$. The respective counts of unital algebra homomorphisms are two, four, and eight, matching the evaluation classification. The all-size result rests on the proof above.
549 
550 \chapter{Weighted witness fingerprints}
551 \label{c:ch:fingerprint}\claim{C07}
552 \section{A polynomial that distinguishes witnesses}
553 Let $R:\B^m\to\B$ be a Boolean verifier, and let $K$ be a characteristic-two field. Define the formal polynomial
554 \[
555  P_R(z_1,\ldots,z_m)=
556  \sum_{w\in\B^m}R(w)\prod_{i=1}^m z_i^{w_i}\in K[z_1,\ldots,z_m].
557 \]
558 The variables $z_i$ in this expression are ordinary polynomial variables, not reduced by $z_i^2=z_i$.
559 
560 \begin{theorem}[Exact witness fingerprint]\label{c:thm:fingerprint}
561 The polynomial $P_R$ is identically zero if and only if $R$ has no accepting witness. Its total degree is at most $m$.
562 \end{theorem}
563 \begin{proof}
564 Different Boolean witnesses have different exponent vectors, so their monomials are distinct. Each accepting witness contributes coefficient one to its own monomial and cannot cancel another witness's term. The polynomial is zero exactly when there are no such terms. Each monomial uses at most $m$ variables.
565 \end{proof}
566 This avoids the cancellation of an unweighted parity count. It does not, by itself, give a small circuit for evaluating the sum.
567 
568 \section{Exact top-coefficient extraction}
569 \begin{lemma}[Top coefficient as a Boolean-cube sum]\label{c:lem:top-coeff}
570 Let $G(w)$ be a multilinear polynomial over a characteristic-two field. Then
571 \[
572  [w_1\cdots w_m]G=\sum_{v\in\B^m}G(v).
573 \]
574 \end{lemma}
575 \begin{proof}
576 It is enough to check a monomial. A monomial of proper support is one on an even number $2^{m-|S|}$ of Boolean inputs, so its cube sum is zero in characteristic two. The full-support monomial is one at exactly one input and has cube sum one. Linearity gives the identity.
577 \end{proof}
578 
579 \begin{theorem}[Weighted top-coefficient identity]\label{c:thm:weighted-top}
580 Let $\KTop_w$ extract the coefficient of $w_1\cdots w_m$ after reduction in the Boolean $w$ algebra. Then
581 \begin{equation}\label{c:eq:weighted-top}
582  P_R(z)=\KTop_w\left[
583  R(w)\prod_{i=1}^m\bigl(1+(1+z_i)w_i\bigr)
584  \right].
585 \end{equation}
586 \end{theorem}
587 \begin{proof}
588 At $w_i=0$, the $i$th factor is one. At $w_i=1$, it is $z_i$. Lemma~\ref{c:lem:top-coeff} therefore converts the right side to exactly the weighted sum defining $P_R$.
589 \end{proof}
590 
591 The expression inside $\KTop_w$ has a circuit with $O(|R|+m)$ operations when the verifier has circuit size $|R|$. The cost of applying $\KTop_w$ to that succinct expression is not bounded by writing down the operator. The source evaluator explicitly stores $2^m$ coefficients and remains exponential in witness length.
592 
593 \section{The conditional algorithmic consequence}
594 \begin{lemma}[Finite-field root bound]\label{c:lem:roots}
595 If a nonzero polynomial $P\in K[z_1,\ldots,z_m]$ has total degree at most $d$, where $K$ is finite, then
596 \[
597  \Pr_{z\text{ uniform in }K^m}[P(z)=0]\le\frac d{|K|}.
598 \]
599 \end{lemma}
600 \begin{proof}
601 Induct on the number of variables. For one variable this is the elementary root bound. In the inductive step, write
602 \[
603  P=\sum_{j=0}^r P_j(z_1,\ldots,z_{m-1})z_m^j,
604  \qquad P_r\ne0.
605 \]
606 The leading coefficient has total degree at most $d-r$, so it vanishes at a random first $(m-1)$-tuple with probability at most $(d-r)/|K|$. Otherwise the remaining univariate polynomial is nonzero with at most $r$ roots. The union bound gives $(d-r+r)/|K|=d/|K|$.
607 \end{proof}
608 
609 \begin{proposition}[Conditional randomized satisfiability test]\label{c:prop:conditional-sat}
610 Suppose the weighted expression in \eqref{c:eq:weighted-top} can be evaluated exactly and uniformly in time polynomial in the verifier description and witness length, over explicitly represented characteristic-two fields of polynomial size. Then choosing $|K|\ge4m$ gives a one-sided randomized polynomial-time satisfiability test. It never accepts an unsatisfiable verifier and accepts a satisfiable one with probability at least $3/4$ per evaluation.
611 \end{proposition}
612 \begin{proof}
613 Choose a uniformly random $z\in K^m$, evaluate $P_R(z)$ under the assumed algorithm, and accept when it is nonzero. If no witness accepts, Theorem~\ref{c:thm:fingerprint} makes the polynomial zero identically, so there is no false acceptance. Otherwise Lemma~\ref{c:lem:roots} bounds the rejection probability by $m/|K|\le1/4$. A field of polynomial size uses $O(\log m)$ bits per element, so the random input has $O(m\log m)$ bits. Under the explicit efficient-field and evaluator hypotheses, the procedure has polynomial running time.
614 \end{proof}
615 
616 \begin{circuitscopebox}{Conditional means the evaluator is still missing}
617 The proposition assumes a uniform efficient evaluator that has not been constructed here. The implemented evaluator is exponential. Even with the assumed evaluator, the stated conclusion is randomized with one-sided error, not a deterministic proof of $P=NP$.
618 \end{circuitscopebox}
619 
620 The exact tests use $\mathrm{GF}(16)=\F[t]/(t^4+t+1)$. They evaluate every specified verifier through three witness bits at every field point, while the independent top-coefficient check uses all field points through two witness bits and the declared smaller coordinate grid at three bits. These domains must not be conflated.
621 
622 \chapter{The overlap obstruction to composition}
623 \label{c:ch:overlap}\claim{C08}
624 The weighted fingerprint is compatible with products on disjoint witness coordinates. The same formula fails when the factors share a coordinate. The distinction isolates a concrete compatibility obligation, rather than asserting that all compression is impossible.
625 
626 \begin{proposition}[Disjoint-variable factorization]\label{c:prop:disjoint}
627 If predicates $A(u)$ and $B(v)$ use disjoint witness-variable sets, then their weighted fingerprints satisfy
628 \[
629  P_{A\land B}(z_u,z_v)=P_A(z_u)P_B(z_v).
630 \]
631 \end{proposition}
632 \begin{proof}
633 Expand the left side as a sum over the Cartesian product of witnesses:
634 \[
635  \sum_{u,v}A(u)B(v)z_u^uz_v^v
636  =\left(\sum_uA(u)z_u^u\right)
637   \left(\sum_vB(v)z_v^v\right).
638 \]
639 Disjointness makes the exponent data independent and the factorization exact.
640 \end{proof}
641 
642 \begin{counterexample}[Shared-variable multiplication fails]\label{c:ce:overlap}
643 For a single witness bit, define $\KTr_z(A)=A(0)+zA(1)$. Then in the Boolean $w$ algebra,
644 \[
645  \KTr_z(w)=z,\qquad \KTr_z(1+w)=1,
646 \]
647 but
648 \[
649  \KTr_z\bigl(w(1+w)\bigr)=0
650  \ne z=\KTr_z(w)\KTr_z(1+w)
651 \]
652 whenever $z\ne0$. Also,
653 \[
654  \KTr_z(w^2)=z,\qquad\KTr_z(w)^2=z^2,
655 \]
656 which differ for field elements $z$ with $z^2\ne z$.
657 \end{counterexample}
658 \begin{proof}
659 Evaluate $w$ and $1+w$ at zero and one. In the Boolean quotient $w(1+w)=w+w^2=0$ and $w^2=w$. The displayed identities follow directly. In $\mathrm{GF}(16)$, any element outside $\F$ supplies the second inequality.
660 \end{proof}
661 
662 The input predicates are individually easy and their separate fingerprints are explicit. Their conjunction nevertheless imposes a common-witness requirement that ordinary multiplication of the summaries fails to preserve.
663 
664 Theorem~\ref{c:thm:gluing-dim} explains a related all-size restriction: a fixed linear multiplicative summary retaining every witness cannot reduce the full witness algebra below dimension $2^m$. That statement does not rule out all context-dependent nonlinear evaluation methods. It rules out the displayed context-free multiplicative compiler under its exact hypotheses.
665 
666 The eight maintained claim groups end here. Their proofs do not assume a superpolynomial shared-generation bound or a polynomial-time weighted-trace evaluator. The appendices identify the exact source coverage, evidence, and closed-scope boundaries.
667 

Back to source controls

Back to Quantum and Circuits