13.4 The degree bound used throughout
On this page · Permalink · Source line 54
Lemma 13.2: Degree per multiplication
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.
Proof
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.
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\).
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.
The source identifies this standard degree bound with the XOR–AND background in [52].