The complete linear core
On this page · Permalink · Source line 907
9.1 Introduction
On this page · Permalink · Source line 908
A CNOT circuit on \(n\) labeled wires represents an element of \({\operatorname{GL}}_n({\mathbb F}_2)={\operatorname{SL}}_n({\mathbb F}_2)\), and minimizing its gate count is the word-metric problem for transvection generators. This formulation supports asymptotically efficient synthesis, architecture-aware elimination, computable lower bounds, and exact small-width optimization [40], [38], [32], [29], [21], [23], [25], [44]. Recent work has also produced stronger explicit lower-bound families and established NP-completeness of exact all-to-all CNOT distance [33], [27], [18]. The present paper studies a different comparison: the target is lower unitriangular, but the circuit is either required to respect that ordered structure or allowed to leave it temporarily.
Let \(R\) be a nonzero commutative ring with identity. A row transvection is
acting by
The transvection is lower directed when \(s<t\). The lower-directed gates generate \({\operatorname{U}}_n(R)\). We compare
with
For a field \({\mathbb F}\), the first metric is intrinsic to the unipotent radical and the second is induced from the elementary group \({\operatorname{E}}_n({\mathbb F})={\operatorname{SL}}_n({\mathbb F})\).
The equality \({\ell_{\downarrow}}(A)={\ell_{*}}(A)\) is tempting because the target and the obvious Gaussian-elimination paths are lower unitriangular. It is false. The failure first occurs at six wires over \({\mathbb F}_2\) and \({\mathbb F}_3\), and it is caused by a reusable temporary carrier rather than by a better ordering of the same lower gates.
Main results
On this page · Permalink · Source line 937
The first result is entirely analytic and does not require a field.
Theorem 9.1: Universal catalytic atom over rings
For every nonzero commutative ring \(R\) with identity, let
Then
The six-gate ambient circuit uses row \(1\) as a dirty workspace. It first adds row \(2\) into row \(1\), exports the carrier \(e_1+e_2\), changes the carrier to \(e_0+e_1+e_2\), exports it twice, and finally removes the temporary \(e_2\) component. No extra wire is introduced. The workspace is one of the target rows and is restored to its prescribed value.
The next result is computer assisted. All state spaces are finite, every transition is exact, and the complete source is included in the ancillary archive.
Theorem 9.2: Exact binary threshold and census
Over \({\mathbb F}_2\):
\({\ell_{\downarrow}}(A)={\ell_{*}}(A)\) for every \(A\in{\operatorname{U}}_n({\mathbb F}_2)\) when \(n\le5\).
Among the \(2^{15}=32768\) matrices in \({\operatorname{U}}_6({\mathbb F}_2)\), exactly twenty satisfy \({\ell_{\downarrow}}(A)>{\ell_{*}}(A)\).
Every defective target satisfies
\[ {\ell_{\downarrow}}(A)=7, \qquad {\ell_{*}}(A)=6. \]No other distance pair is defective.
The twenty targets have a uniform combinatorial explanation.
Theorem 9.3: Minimal catalytic classification
The twenty defective targets in \({\operatorname{U}}_6({\mathbb F}_2)\) are exactly the targets generated by a simple one-catalyst word having three cross interactions, one phase interaction, and a nontrivial before/after split across the phase. The numbers arising from the three possible left/right auxiliary splits are
for a total of twenty.
The field-independent atom and exact ternary search also give the same finite threshold over \({\mathbb F}_3\).
Theorem 9.4: Exact ternary threshold
For \(n\le5\) and every \(A\in{\operatorname{U}}_n({\mathbb F}_3)\),
The matrix \(C\in{\operatorname{U}}_6({\mathbb F}_3)\) of Equation (9.1) has distances \((7,6)\). Hence six is the first defective dimension over \({\mathbb F}_3\).
To pass from the first threshold to arbitrarily large connected examples, we introduce a multiscale rank certificate and a family that exports successive carrier states.
Theorem 9.5: Connected snapshot family
Let \(u\ge1\), let \(1\le v\le u+1\), and choose distinct phases
There is a connected target
with
and
Hence its certified defect is at least \(v-2\).
Corollary 9.6: Connected defects in every dimension
For every field and every \(n\ge7\), there is a connected target \(A_n\in{\operatorname{U}}_n({\mathbb F})\) satisfying
The same construction remains effective under stringent restrictions on the ambient resource.
Theorem 9.7: Two forbidden gates and weighted penalties
For every field and every \(n\ge7\), there is a connected target \(A_n\in{\operatorname{U}}_n({\mathbb F})\) such that
where \({\ell_{\le q}}\) permits at most \(q\) upper-directed gates. More generally, if lower gates have cost \(1\) and upper gates have cost \(\lambda>0\), then
Thus no fixed upper-gate budget of two, and no fixed finite upper-gate penalty, suppresses catalytic escape asymptotically.
The same paths remain extremely close to the restricted subgroup. For a matrix \(X\) over a field, let \(X^+\) be its strict upper part, let \(r^+(X)={\operatorname{rank}} X^+\), and let \(b^+(X)\) be the largest upper displacement \(j-i\) with \(X_{ij}\ne0\). If \({\ell^{(r,b)}}\) denotes the minimum length among circuits satisfying \(r^+(X_t)\le r\) and \(b^+(X_t)\le b\) at every prefix, then the connected family can be chosen so that
Thus a rank-one excursion across one adjacent flag layer can create a linear saving.
At fixed dimension, however, defects occupy thin algebraic strata.
Theorem 9.8: Generic rigidity and defect codimension
Let \(K\) be an infinite field and put \(N=\binom n2\). There is a nonempty Zariski-open subset \(\Omega_n\subseteq{\operatorname{U}}_n\) with \(\Omega_n(K)\ne\varnothing\) such that
Moreover, after base change to an algebraic closure \(\overline K\), for
one has
Corollary 9.9: Finite-field sparsity
Let \(N=\binom n2\) and \(M=n(n-1)\). For \(1\le d\le N\),
For fixed \(n\), a uniformly random target therefore has defect zero with probability \(1-O_n(q^{-1})\) as \(q\to\infty\).
Tensor products produce a stronger asymptotic separation.
Theorem 9.10: Tensor-amplified snapshot family
Let \(A=A(u;s_1,\ldots,s_v)\) have dimension \(m=u+v+2\). For \(N=m^r\),
while
Consequently,
Corollary 9.11: Explicit \(n\log n\) distortion
For
one has, for every field and every \(n\),
The coefficient is attained within the snapshot family by the twenty-one-dimensional seed
Conceptual interpretation
On this page · Permalink · Source line 1136
The ambient circuit is shorter because one forbidden-direction gate creates a carrier that is read by several later gates before it is cleaned. The saving is therefore a reuse effect. The relevant object is not an ancillary wire in the usual sense. It is a temporary excursion from a flag-preserving frame space into the full frame graph.
Over \({\mathbb F}_2\), the carrier states used by the canonical word form six of the seven points of \(\operatorname{PG}(2,2)\). The four projective lines supported on those six points form a Pasch configuration. The same six vectors represent the graphic matroid \(M(K_4)\) over every field; this regular-matroid structure isolates the characteristic-independent core of the atom. At the spectral level, the distance to a target is the first nonzero coefficient of an endpoint Green kernel. For \(C\), the ambient kernel begins in degree six and the restricted kernel begins in degree seven.
The higher-dimensional families reveal three additional principles. First, an interval-tree certificate can make the restricted metric exactly additive across scales even when the target is connected. Second, two forbidden gates can support a linear saving, even if each forbidden gate carries any fixed finite penalty. Third, tensor products add normalized restricted complexity while ambient complexity remains subadditive. This converts one local carrier advantage into a superlinear global defect. Finally, the algebraic-geometric bounds show that these amplifiable atoms are exceptional at fixed dimension: a defect of size \(d\) imposes at least \(d\) algebraic codimensions. The resulting picture is one of algebraic rarity coupled with asymptotic amplification.
Scope
On this page · Permalink · Source line 1144
The results concern in-place reversible linear circuits on labeled rows. They do not by themselves imply a faster general CNOT synthesis algorithm, a lower bound for unrestricted XOR directed acyclic graphs, or a result about integer multiplication. Their content is a precise comparison between a flag-preserving gate model and the ambient transvection model.
The paper is organized as follows. Section 9.2 fixes the circuit and metric conventions and gives the Schreier-holonomy interpretation. Section 9.3 proves the universal ring-valued atom. Section 9.4 develops the catalytic normal form and counts the twenty minimal motifs. Section 9.5 gives the exact binary and ternary enumerations and proves the search procedure complete. Section 9.6 gives the projective, regular-matroid, and Green-kernel formulations. Section 9.7 develops interval-tree certificates, exact cases through dimension nine, and connected families in every larger dimension. Section 9.8 proves bounded, weighted, and microscopic-excursion theorems. Section 9.9 proves generic rigidity, defect-codimension bounds, and finite-field sparsity. Section 9.10 proves block, recursive, and tensor amplification, introduces stable tensor capacity, and derives the \(n\log n\) extremal bound. The appendices provide the exact target list, algorithms, and reproducibility data.
Proof and computation status
On this page · Permalink · Source line 1150
The universal atom, catalytic identities, interval-tree certificates, connected families, resource bounds, algebraic-rarity theorems, amplification results, and stable tensor limit are proved symbolically. Complete search is used only for the first-threshold censuses, the equality between the twenty computed defects and the twenty analytic motifs, and the exact ambient distances of the selected seven-, eight-, and nine-dimensional targets. Every computer-assisted statement is paired with a finite-state completeness argument and a reproducible implementation in the supplement.