Model and definitions
On this page · Permalink · Source line 58
THE ASSUMPTIONS ARE PART OF THE THEOREM A general register state is a Boolean function \(W\to\mathrm{Bool}\) on any wire type with decidable equality. C01 does not assume that \(W\) is finite. The canonical degree model has a finite wire set with \(n\) input wires, \(a\) ancillas, and one target. A NOT complements a bit. A CNOT adds one control to a distinct target. A Toffoli adds the product of two distinct controls to a third distinct wire. Gate constructors carry the required inequalities.
All arithmetic is over \(\mathbb F_2\), implemented using Boolean XOR and AND. Each gate is its own inverse. Circuit reversal, restoration, and every cut are inherited from the unchanged Block 01 source.
| Quantity | Meaning in the formal source |
|---|---|
| \(T\) | Toffoli count. NOT and CNOT have cost zero in this count only. |
| \({\operatorname{DegreeLE}}(d,f)\) | \(f\) is an XOR of finitely many monomials, each containing at most \(d\) variable occurrences. |
| Safe detector | A Boolean \(h\) with \(h(x)=1\Rightarrow f(x)=1\). |
| Complete coverage | Every positive \(v\) has a safe detector with \(h(v)=1\). |
| \(\beta(f)\) | Least degree bound sufficient for complete safe coverage. |
| \(\beta^*(f)\) | Least upper bound on \(\beta(f{\mathbin{\oplus}} g)\) over all degree-one \(g\). |
Polynomial certificates are not postulated degree oracles
On this page · Permalink · Source line 73
The inductive certificate has three constructors: zero, a bounded-length monomial, and XOR of two certified functions. It is tied to the concrete evaluator
by a proved equivalence. A certificate yields an explicit finite monomial list, and such a list yields a certificate.
Repeated variables are allowed in the list. Boolean idempotence reduces their repetitions without increasing degree. This is the representation form of the usual Boolean degree bound. The formal source does not separately implement canonical ANF normalization or claim that extracting every homogeneous grade is free.
Boundary of the model
On this page · Permalink · Source line 82
There are no quantum phases, measurements, or discarded work registers. Inputs and zero ancillas restore for every logical input and both target values. Standard classical choice defines least semantic bounds, but supplies no polynomial-time procedure for finding their witnesses.