10.3 Temporary nonlinearity: affine logic versus Toffoli-assisted synthesis
On this page · Permalink · Source line 3688
10.3.1 The question
On this page · Permalink · Source line 3695
Let
be the affine reversible group. It is generated by NOT and CNOT gates. The ambient gate set adds Toffoli. On three bits it generates the full reversible group. On \(n\ge4\) bits with no ancillas, each NOT, CNOT, or Toffoli gate is an even permutation, so this alphabet does not generate the full symmetric group.
The catalytic question is:
Can a circuit temporarily create nonlinear Boolean terms with Toffoli gates, reuse them, cancel them completely, and implement a final affine permutation with fewer gates than every affine circuit?
This is the nonlinear analogue of dirty linear memory.
10.3.2 Algebraic normal form
On this page · Permalink · Source line 3710
Every Boolean coordinate function has a unique algebraic normal form
Affine maps have degree at most one. A Toffoli gate targeting \(t\) with controls \(a,b\) performs
which can raise the degree of later coordinates. The final affine target requires every higher-degree coefficient to cancel.
A candidate lower-bound invariant must do more than track maximum degree. One Toffoli creates degree two and a second can remove it. Useful refinements include:
the dimension of the quadratic monomial span,
directional derivatives \(D_u f(x)=f(x+u)+f(x)\),
the rank of the bilinear polarization,
the number of outputs consuming a nonlinear workspace term,
restoration obligations for every nonlinear carrier.
10.3.3 Exact three-bit census
On this page · Permalink · Source line 3732
On three bits,
while the group generated by NOT, CNOT, and Toffoli is the full permutation group
Both spaces can be enumerated exactly.
Exact finite computation
For three bits, every affine target has the same minimum cost in the affine gate set and in the Toffoli-assisted gate set under each of the following metrics:
total primitive gate count, where NOT, CNOT, and Toffoli cost one,
entangling count, where NOT is free and CNOT and Toffoli cost one.
There are no defective affine targets among all \(1344\) targets.
The restricted total-count diameter is seven and the ambient diameter on \(S_8\) is eight. Under entangling count, both relevant diameters are six. Equality on affine targets is stronger than a diameter comparison because every target is checked individually.
10.3.4 Interpretation of the negative result
On this page · Permalink · Source line 3764
The census does not show that temporary nonlinearity is useless in general. It shows that three bits do not provide enough state space for a nonlinear carrier to repay its creation and cancellation cost under the stated alphabets.
The negative result is valuable for three reasons.
It gives a certified lower threshold: any total- or entangling-count defect requires at least four bits.
It prevents a forced analogy with the six-wire linear catalyst.
It supplies a complete regression test for future synthesis code.
10.3.5 A formal nonlinear catalyst
On this page · Permalink · Source line 3774
A clean one-workspace template is
where \(T\) is Toffoli and the middle gates use the quadratic term created in the workspace. Since Toffoli is self-inverse, the displayed circuit uses two nonlinear gates.
The key difficulty is that a final affine map cannot retain any product term. Every output that consumed the nonlinear carrier must be repaired, or the nonlinear contributions must cancel collectively.
10.3.6 Conjugation formulas
On this page · Permalink · Source line 3790
Let \(T_{ab\to t}\) denote Toffoli. Conjugating an affine gate by \(T\) can produce nonlinear permutations. For example, if \(X_t\) flips the target,
so no gain occurs. If a CNOT changes a control or exports the target, the conjugated map can contain several quadratic terms. The exact formula is easiest in algebraic normal form: substitute the Toffoli-updated coordinate into the affine map, then apply the inverse substitution.
A systematic search should classify pairs \((T,h)\) for which
For one Toffoli and an affine middle word, this is a normalizer-intersection problem. A useful next bounded test is to examine simple two-Toffoli sandwiches with an affine middle word of restricted length at most five. The present archive contains no reproducible implementation or receipt for this four-bit test, so no negative result from it is claimed here.
10.3.7 Potential lower-bound invariants
On this page · Permalink · Source line 3803
10.3.7.1 Quadratic support debt
On this page · Permalink · Source line 3804
Let \(Q(f)\) be the span of quadratic monomials appearing across the coordinate functions. A Toffoli changes \(Q(f)\) by at most a controlled rank-one contribution before subsequent substitutions. If several outputs consume the same quadratic term, a dynamic debt invariant may charge its creation, distribution, and cancellation.
10.3.7.2 Derivative rank
On this page · Permalink · Source line 3807
For an affine map, every derivative \(D_u f\) is constant. During a nonlinear excursion, the derivative map
can depend on \(x\). One can track the dimension of the nonconstant derivative space and require it to return to zero.
10.3.7.3 Higher-order Möbius coefficients
On this page · Permalink · Source line 3814
The ANF coefficients are the Möbius transform of the truth table. Projectors onto degree layers give an exact packet decomposition
A restricted affine circuit remains in degrees zero and one. The ambient circuit can populate higher packets temporarily. A successful lower bound must charge the useful flow through those packets, not merely their instantaneous dimension.
10.3.8 Four-bit search architecture
On this page · Permalink · Source line 3821
The full permutation group on four-bit states has size \(16!\). The declared no-ancilla gate alphabet lies in its alternating subgroup: NOT, CNOT, and Toffoli are respectively products of eight, four, and two disjoint transpositions. Even this reduced ambient search is large enough to require a more structured approach. Several exact approaches remain available.
Meet in the middle for a fixed candidate target and length.
SAT or SMT encoding of a length-\(L\) circuit with affine endpoint constraints.
Bidirectional search restricted to states within a bounded nonlinear-degree or Toffoli-count budget.
Enumeration of two- or four-Toffoli normal forms modulo affine conjugation.
Mixed-integer or algebraic solving of ANF coefficient equations.
Protocol 10.10: First four-bit threshold search
Compute exact affine distances for all \(322{,}560\) affine targets.
Enumerate ambient words with two Toffoli gates modulo affine gates on the left and right.
Retain words whose endpoint is affine.
Compare with the exact affine distance.
If no defect appears, increase the Toffoli budget and produce an unsatisfiability certificate for every shorter length.
This protocol is a research plan. The packaged executable census stops at three bits, and neither the four-bit normal-form search nor its lower-bound certificates is supplied.
10.3.9 Resource variants
On this page · Permalink · Source line 3842
Temporary nonlinearity may be useful under one metric and useless under another. Natural costs include:
A Toffoli-assisted affine shortcut in total Boolean gates might disappear after fault-tolerant decomposition. Conversely, a circuit with more Boolean primitives can reduce \(T\)-depth.
10.3.10 Related nonlinear gate families
On this page · Permalink · Source line 3853
The same program applies to:
CCZ-assisted diagonal Boolean phase maps,
relative-phase Toffoli gates,
multi-controlled \(X\) and \(Z\) gates,
Reed–Muller degree hierarchies,
reversible arithmetic over \({\mathbb Z}_d\),
polynomial automorphisms over finite rings.
Conjectural frontier
There exists an affine target on finitely many bits whose total or fault-tolerant resource cost is reduced by a restored nonlinear excursion. The exact three-bit census rules out the smallest possible instance but supplies no evidence for a particular larger threshold.
10.3.11 Reproducible code
On this page · Permalink · Source line 3868
The implementation represents every reversible map as an exact permutation of \(2^n\) basis states. Breadth-first search enumerates both the affine group and the full three-bit reversible group.
Exact three-bit affine-versus-Toffoli census.
On this page · Permalink · Source line 3871
from catalytic_gate_atlas import exact_affine_toffoli_census
print(exact_affine_toffoli_census(3, entangling_cost=False))
print(exact_affine_toffoli_census(3, entangling_cost=True))The expected defect count is zero in both outputs.