The model: boundary restoration and Boolean degree
On this page · Permalink · Source line 1
A state has logical input wires \(x\), zero-initialized ancillary wires, and a target bit \(y\). A restored oracle is a legal classical circuit satisfying
The input and scratch restoration conditions hold at the boundary. Wires may change internally, and the target may control an intermediate gate. Each primitive gate is an involution:
In a CNOT the control differs from the target. In a Toffoli all three wires are distinct. These are construction rules, not informal assumptions.
All polynomial arithmetic in the Boolean state model is over \({\mathbb F}_2\), with \(x_i^2=x_i\). Every function has a unique multilinear algebraic normal form. Its degree is the largest support size with a nonzero coefficient; the zero function has mathematical degree \(-1\) in the Python helpers. A formal degree bound uses a natural number, so zero has a degree-zero certificate.
| Quantity | Meaning |
|---|---|
| \(T\) | Number of Toffoli gates; NOT and CNOT have zero cost in this quantity |
| \(L\) | Total number of NOT, CNOT, and Toffoli gates |
| \(M\) | Number of binary AND operations in an XOR–AND computation |
| \(n\) | Actual number of input bits, including all variables in a displayed family |
| \(\dim_K A\) | Dimension of a specified linear summary algebra over \(K\) |
A bound on one row of this table cannot silently be substituted for a bound on another row. In particular, a computation can have few Toffolis and many CNOTs. An exponentially large ambient algebra can have succinct expressions. Those distinctions explain the projection and gluing examples later.