Degree bounds must retain shared register products
On this page · Permalink · Source line 167
Take four independent input bits. Compute
After two ANDs, each nonlinear register has degree two, but their product has degree four. After the third AND, a coordinate of degree four appears.
The correct invariant tracks a product of \(r\) current registers after \(t\) Toffolis:
At \(t=2\), the product \(q_1q_2\) has \(r=2\) and saturates \(t+r=4\). At \(t=3\), the resulting coordinate has \(r=1\) and saturates \(t+1=4\).
This explains why tracking only individual register degrees and then adding their separate histories can lose the shared accounting. The invariant applies to the actual evolving state. It does not unfold a reused register into a new copy of the entire computation.
Exact finite fixture plus the general register-product invariant; the source proves workspaceDegree_run for arbitrary gate lists.