Quantum and Circuits

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

Read the typeset paper

Read this chapter with formatted equations

1 \chapter{General theory of temporary escape}
2 \section{Nested gate models and distortion invariants}\label{g:ch:nested-models}
3 \index{gate-set distortion}
4 \index{restricted realization}
5 \index{ambient realization}
6 \index{cost vector}
7 \index{existence defect}
8 
9 
10 \subsection{Why a separate theory is needed}
11 A target transformation often belongs to a visibly structured class even when the machine used to realize it is capable of much more.  A lower-triangular linear transformation may be synthesized by an unrestricted CNOT network.  A diagonal unitary may be realized by a non-diagonal Clifford+$T$ circuit.  A charge-preserving unitary may be compiled by gates that temporarily visit other charge sectors.  A Gaussian target may be realized by a circuit that briefly uses a non-Gaussian primitive.  These situations share a question that is not answered by ordinary exact synthesis:
12 \begin{quote}
13 How much does it cost to require the \emph{entire path} of a computation to retain the structure possessed by its endpoint?
14 \end{quote}
15 The distinction is path dependent.  It is not determined only by membership of the final target in a subgroup, a subcategory, or a model class.
16 
17 \begin{figure}[ht]
18 \centering
19 \includegraphics[width=.90\textwidth]{assets/g_gate_hierarchy.pdf}
20 \caption{A restricted model inside an ambient model. The target lies in the restricted class, while an ambient implementation may leave it temporarily and return. Each gate family requires its own specified inclusion and costs.}
21 \label{g:fig:gate-hierarchy}
22 \end{figure}
23 
24 \subsection{Exact gate models}
25 \begin{definition}[Gate model]
26 An \emph{exact gate model} is a tuple
27 \[
28 \mathfrak M=(\mathcal X,\mathcal S,c,\circ),
29 \]
30 where $\mathcal X$ is a set of states or morphisms, $\mathcal S$ is a specified family of elementary generators, $c:\mathcal S\to\R_{\ge0}$ is a cost function, and $\circ$ is the composition law.  A word
31 \[
32 w=s_L\cdots s_1
33 \]
34 has cost
35 \[
36 c(w)=\sum_{j=1}^L c(s_j).
37 \]
38 For a target $U\in\mathcal X$, the exact synthesis cost is
39 \[
40 \ell_{\mathfrak M}(U)=\inf\{c(w):w=U\}.
41 \]
42 The value is $+\infty$ when the target has no realization.
43 \end{definition}
44 
45 The composition law may be group multiplication, composition of permutations, composition of quantum channels, tensor-network contraction, or composition in a dagger symmetric monoidal category.  The additive cost may count all gates, only entangling gates, only non-Clifford gates, weighted error, or a vector of several resources.  Depth fits this additive model by taking admissible parallel layers as generators, rather than charging one unit to each individual gate.
46 
47 \begin{definition}[Nested realization pair]
48 A \emph{nested realization pair} consists of restricted and ambient models
49 \[
50 \mathfrak M_{\mathrm{res}}\subseteq\mathfrak M_{\mathrm{amb}}
51 \]
52 with a common target class $\mathcal T$ of finite ambient cost and the same cost on common generators.  For $U\in\mathcal T$, define
53 \[
54 \ellRes(U)=\ell_{\mathfrak M_{\mathrm{res}}}(U),
55 \qquad
56 \ellAmb(U)=\ell_{\mathfrak M_{\mathrm{amb}}}(U).
57 \]
58 The additive defect is
59 \[
60 \Delta(U)=\ellRes(U)-\ellAmb(U).
61 \]
62 \end{definition}
63 
64 When both costs are finite, $\Delta(U)$ is a metric or optimization defect.  If $\ellRes(U)=+\infty$ and $\ellAmb(U)<+\infty$, it is an existence defect.  This convention unifies finite gate savings with the failure of a restricted realization category.
65 
66 \begin{proposition}[Monotonicity]
67 For every target in the common domain,
68 \[
69 \ellAmb(U)\le \ellRes(U).
70 \]
71 Consequently $\Delta(U)\ge0$ whenever both models use the same nonnegative cost on their common generators.
72 \end{proposition}
73 \begin{proof}
74 Every restricted word is also an ambient word.
75 \end{proof}
76 
77 \subsection{Cost models are part of the theorem}
78 A gate-set comparison is incomplete until the cost convention is fixed.  The same pair of groups can display a defect under entangling count and no defect under total primitive count.  A SWAP gate may be primitive, may cost three CNOTs, or may be implemented by physical motion.  A local Clifford may be free in a fault-tolerant resource estimate and nonfree in a pulse-level model.
79 
80 \begin{definition}[Resource vector]
81 Let
82 \[
83 \mathbf c(s)=(c_1(s),\ldots,c_r(s))\in\R_{\ge0}^r
84 \]
85 be the resource vector of a gate.  The achievable resource region of a target is
86 \[
87 \mathcal P_{\mathfrak M}(U)
88 =
89 \left\{
90 \sum_{j=1}^L\mathbf c(s_j):s_L\cdots s_1=U
91 \right\}.
92 \]
93 Its nondominated points form the Pareto boundary.
94 \end{definition}
95 
96 For a weight vector $\lambda\in\R_{\ge0}^r$, scalarization gives
97 \[
98 \ell_{\mathfrak M}^{\lambda}(U)
99 =
100 \inf_{x\in\mathcal P_{\mathfrak M}(U)}\lambda\cdot x.
101 \]
102 The scalar defect $\Delta^\lambda(U)$ can vary with $\lambda$ even when the target and gate alphabets are fixed.
103 
104 \begin{figure}[ht]
105 \centering
106 \includegraphics[width=.74\textwidth]{assets/g_resource_pareto.pdf}
107 \caption{Restricted and ambient Pareto regions can differ without one model dominating by the same amount under every resource weighting.}
108 \label{g:fig:pareto}
109 \end{figure}
110 
111 \begin{principle}[Model specificity]
112 Every claimed shortcut must state the target class, elementary gate alphabet, ancilla convention, exact or approximate synthesis criterion, and cost vector.  Changing any one of these may remove, create, or reverse a defect.
113 \end{principle}
114 
115 \subsection{Ancilla and restoration conventions}
116 Temporary workspace is meaningful only after its restoration rule is specified.
117 \begin{definition}[Ancilla conventions]
118 An ancilla is
119 \begin{enumerate}
120 \item \emph{clean} if it begins in a specified state and must return to that state,
121 \item \emph{borrowed} or \emph{dirty} if its initial state is arbitrary but must be restored,
122 \item \emph{consumable} if restoration is not required,
123 \item \emph{catalytic} if it is restored while enabling a cheaper realization of the target.
124 \end{enumerate}
125 \end{definition}
126 The present theory focuses on restoration.  If an auxiliary resource may be discarded, the comparison becomes a different channel or isometry synthesis problem.
127 
128 \subsection{Worst-case and threshold functions}
129 For a size parameter $n$, let $\mathcal T_n$ denote the target family.
130 \begin{definition}[Extremal distortion]
131 Define
132 \[
133 D_n=\sup_{U\in\mathcal T_n}\Delta(U)
134 \]
135 and, when $0<\ellAmb(U)<\infty$,
136 \[
137 R_n=\sup_{U\in\mathcal T_n}
138 \frac{\ellRes(U)}{\ellAmb(U)}.
139 \]
140 The first defective size is
141 \[
142 \tau=\min\{n:D_n>0\}.
143 \]
144 We set a threshold to $+\infty$ when its defining set is empty.
145 \end{definition}
146 
147 Several threshold notions should not be conflated:
148 \begin{align*}
149 \tau_{\mathrm{metric}}&=\min\{n:\exists U,\ 0<\Delta(U)<\infty\},\\
150 \tau_{\mathrm{exist}}&=\min\{n:\exists U,\ \ellRes(U)=\infty,\ \ellAmb(U)<\infty\},\\
151 \tau_{q}&=\min\{n:\exists U,\ \ell_{\le q}(U)<\ell_{\le0}(U)\},
152 \end{align*}
153 where $\ell_{\le q}$ permits at most $q$ ambient-only gates.  A model may have an early metric threshold and a later existence threshold, or no threshold at all.
154 
155 \subsection{Equivalence, orbits, and classification}
156 A finite census should be quotiented by transformations preserving both gate models and the cost.  Depending on the problem, these may include wire permutations, local Clifford conjugation, isotopy, simultaneous row and column relabeling, or graph automorphisms.
157 
158 \begin{definition}[Cost-preserving equivalence]
159 Targets $U$ and $V$ are equivalent if an automorphism $\varphi$ of the ambient realization system satisfies
160 \[
161 \varphi(U)=V,
162 \qquad
163 \varphi(\mathcal S_{\mathrm{res}})=\mathcal S_{\mathrm{res}},
164 \qquad
165 \varphi(\mathcal S_{\mathrm{amb}})=\mathcal S_{\mathrm{amb}},
166 \]
167 and preserves the gate costs.
168 \end{definition}
169 Under this equivalence, both lengths and the defect are orbit invariants.  A useful threshold theorem should classify minimal defective orbits, not merely list raw matrices.
170 
171 \subsection{Approximate synthesis and border defects}
172 For continuous gate models, exact word length can differ from the minimum length achievable as a limit.
173 \begin{definition}[Border cost]
174 Let $\overline{\mathcal W}_{L}$ be the topological or Zariski closure of targets realizable with cost at most $L$.  The border cost is
175 \[
176 \underline\ell(U)=\inf\{L:U\in\overline{\mathcal W}_{L}\}.
177 \]
178 The border defect is
179 \[
180 \underline\Delta(U)=
181 \underline\ell_{\mathrm{res}}(U)-
182 \underline\ell_{\mathrm{amb}}(U).
183 \]
184 \end{definition}
185 This is the circuit analogue of the distinction between tensor rank and border rank.  An exact defect can disappear under degeneration, persist, or become larger after approximation changes the relevant cost geometry.
186 
187 \subsection{Metric and existence defects in one category}
188 Let $\mathcal C_{\mathrm{res}}\subseteq\mathcal C_{\mathrm{amb}}$ be categories with weighted generating morphisms.  For a morphism $f$ in the restricted target class, the same definition
189 \[
190 \Delta(f)=c_{\mathrm{res}}(f)-c_{\mathrm{amb}}(f)
191 \]
192 includes group-word metrics, adaptive quantum channels, tensor-network realizations, and orthogonality designs.  This categorical form is essential when the ambient model permits measurement, branching, postselection, or entangled objects that do not lie in a common group.
193 
194 \begin{boundarybox}
195 The abstract definition does not prove that a defect exists.  It provides a common language in which a finite search, a symbolic identity, and a lower-bound certificate can be compared without changing the meaning of the target or the cost.
196 \end{boundarybox}
197 
198 \subsection{A standard theorem package}
199 A mature gate-set distortion result should contain as many of the following components as the model allows:
200 \begin{enumerate}
201 \item a precisely defined nested gate pair and cost vector,
202 \item a smallest defective target or a no-defect theorem below a threshold,
203 \item an explicit ambient word,
204 \item a restricted lower-bound certificate,
205 \item classification modulo cost-preserving equivalence,
206 \item a reusable catalytic normal form,
207 \item direct-sum, recursive, or tensor amplification,
208 \item generic-rigidity or sparsity results,
209 \item a certificate-producing implementation,
210 \item a clear account of which statements are symbolic, computed, or conjectural.
211 \end{enumerate}
212 The remainder of the monograph follows this package.
213 
214 \section{Catalytic holonomy, excursion geometry, and resource reuse}\label{g:ch:holonomy}
215 \index{holonomy}
216 \index{Schreier graph}
217 \index{catalytic conjugation}
218 \index{dirty workspace}
219 \index{resource amortization}
220 
221 
222 \subsection{Subgroup metrics and Schreier loops}
223 Assume first that the restricted and ambient models are groups
224 \[
225 H=\langle\mathcal S_H\rangle
226 \le
227 G=\langle\mathcal S_G\rangle.
228 \]
229 For $h\in H$, the intrinsic and ambient word metrics are
230 \[
231 \ell_H(h)=|h|_{\mathcal S_H},
232 \qquad
233 \ell_G(h)=|h|_{\mathcal S_G}.
234 \]
235 In the group-metric statements, the generating alphabets are symmetric and a generator and its inverse have equal cost.  The quotient geometry is the left Schreier graph $G/H$, with edges $gH\longmapsto sgH$.  For the base-fiber assertion below, assume also $\mathcal S_H=\mathcal S_G\cap H$.  This last condition excludes additional ambient primitives that already lie in $H$ but have no equally cheap restricted realization.
236 
237 \begin{theorem}[Holonomy-compression identity]
238 Let every generator have unit cost.  For $h\in H$, $\ell_G(h)$ is the minimum length of a based loop in $G/H$ whose lifted word has holonomy $h$.  The intrinsic length $\ell_H(h)$ is the minimum length among loops that remain in the base fiber.
239 \end{theorem}
240 \begin{proof}
241 An ambient word $s_k\cdots s_1=h$ projects to the loop
242 \[
243 H,
244 s_1H,
245 s_2s_1H,
246 \ldots,
247 hH=H.
248 \]
249 Conversely, a based Schreier loop has product in $H$.  If every prefix lies in $H$, each edge label is the product of two elements of $H$ and belongs to $\mathcal S_G\cap H=\mathcal S_H$.  Conversely every restricted word remains in the base fiber.  Minimizing the labeled words with endpoint $h$ gives the two asserted lengths.
250 \end{proof}
251 
252 Thus
253 \[
254 \Delta_{H\hookrightarrow G}(h)
255 =
256 \text{intrinsic fiber cost}
257 -
258 \text{shortest holonomy loop cost}.
259 \]
260 This is the geometric content of a dirty-workspace shortcut.
261 
262 \begin{figure}[ht]
263 \centering
264 \includegraphics[width=.90\textwidth]{assets/g_catalytic_excursion_general.pdf}
265 \caption{A catalytic excursion leaves a restricted fiber, reuses an ambient state, and returns with nontrivial holonomy.}
266 \label{g:fig:catalytic-excursion}
267 \end{figure}
268 
269 \subsection{The basic conjugation inequality}
270 Let $g\in G$ and $k\in H$ satisfy $gkg^{-1}\in H$.  Then
271 \[
272 \ell_G(gkg^{-1})
273 \le 2\ell_G(g)+\ell_H(k).
274 \]
275 Define the intrinsic conjugation stretch
276 \[
277 \operatorname{Stretch}_g(k)
278 =
279 \ell_H(gkg^{-1})-\ell_H(k).
280 \]
281 
282 \begin{proposition}[Catalytic stretch criterion]
283 If
284 \[
285 \operatorname{Stretch}_g(k)>2\ell_G(g),
286 \]
287 then $gkg^{-1}$ has positive defect.
288 \end{proposition}
289 The opening and closing cost is paid once.  Every useful consumer inside the excursion contributes to the stretch.
290 
291 \subsection{Many consumers and catalytic excess}
292 Suppose the middle word is
293 \[
294 k=h_m\cdots h_1,
295 \qquad h_i\in H.
296 \]
297 The ambient word
298 \[
299 gh_m\cdots h_1g^{-1}
300 \]
301 has cost at most
302 \[
303 2c(g)+\sum_i c(h_i).
304 \]
305 If the restricted images $gh_ig^{-1}$ require costs $r_i$ and a lower-bound invariant proves that their obligations cannot be shared, then
306 \[
307 \ell_H(gkg^{-1})\ge\sum_i r_i.
308 \]
309 A sufficient inequality is
310 \[
311 \sum_i(r_i-c(h_i))>2c(g).
312 \]
313 The left side is the gross catalytic benefit.  The right side is the restoration cost.
314 
315 \begin{definition}[Catalytic excess]
316 For a normal form with $r$ matched excursions and $C$ useful cross interactions, define
317 \[
318 \mathcal E=C-2r
319 \]
320 when each consumer contributes one unit and each opening or closing costs one unit.
321 \end{definition}
322 Positive excess is necessary in the simplest transvection model, but it is not sufficient.  An all-cross configuration may admit a mirror word of equal restricted length.  Temporal asymmetry or phase holonomy is also required.
323 
324 \subsection{Excursion budgets}
325 Counting ambient-only gates is only one measure of how far a circuit leaves its restricted model.
326 \begin{definition}[Excursion profile]
327 For a circuit path $X_0,X_1,\ldots,X_L$, an excursion profile may include
328 \begin{enumerate}
329 \item the number $q$ of ambient-only gates,
330 \item the maximum Schreier distance $d(X_tH,H)$,
331 \item the rank of a forbidden block,
332 \item the bandwidth of a forbidden dependency,
333 \item the number of simultaneously open catalytic intervals,
334 \item the intersection graph of those intervals,
335 \item the maximum algebraic degree created temporarily,
336 \item the maximum ancilla dimension or branch count.
337 \end{enumerate}
338 \end{definition}
339 The established linear family shows that a rank-one, bandwidth-one excursion using exactly two forbidden gates can save linearly many operations.  Thus geometric excursion size need not control computational benefit.
340 
341 \subsection{Catalytic interval geometry}
342 Associate to every matched opening and closing operation an interval
343 \[
344 I_j=[t_j^{\mathrm{open}},t_j^{\mathrm{close}}].
345 \]
346 The family of intervals can be disjoint, nested, laminar, or crossing.
347 
348 \begin{principle}[First higher-order frontier]
349 Independent or disjoint intervals often reduce to additive copies of a one-catalyst analysis.  Crossing intervals are the first place where one dirty resource can alter another and where a multiplicative distortion larger than the clean one-carrier value may occur.
350 \end{principle}
351 
352 Define the catalytic width
353 \[
354 w_{\mathrm{cat}}=
355 \max_t
356 \#\{j:t\in I_j\}.
357 \]
358 One may then study
359 \[
360 D_n^{(w)}
361 =
362 \max_{U}
363 \left(
364 \ellRes(U)-\ellAmb^{(w)}(U)
365 \right),
366 \]
367 where the ambient circuit has width at most $w$.  The unitriangular snapshot family gives $D_n^{(1)}=\Omega(n)$ in its corresponding interval model.
368 
369 \subsection{Four recurrent catalytic mechanisms}
370 \subsubsection{Basis-change catalysis}
371 An ambient gate $g$ changes the frame in which several restricted operations are cheap:
372 \[
373 h_i\mapsto gh_ig^{-1}.
374 \]
375 Hadamard and Fourier transforms are the basic quantum examples.  The frame is restored at the end.
376 
377 \subsubsection{Commutator catalysis}
378 An ambient commutator creates a new direction:
379 \[
380 [g,h]=ghg^{-1}h^{-1}.
381 \]
382 For continuous controls,
383 \[
384 e^{\varepsilon X}e^{\varepsilon Y}e^{-\varepsilon X}e^{-\varepsilon Y}
385 =
386 e^{\varepsilon^2[X,Y]+O(\varepsilon^3)}.
387 \]
388 The desired effective generator may lie in the restricted algebra even though the path does not.
389 
390 \subsubsection{Degree catalysis}
391 A Toffoli, CCZ, or non-Gaussian gate can create higher algebraic degree or higher moments temporarily.  If the nonlinear object is reused and canceled, the final target may remain affine, diagonal, or Gaussian.
392 
393 \subsubsection{Branch and workspace catalysis}
394 Ancillas, measurements, reset, teleportation, and classical feedforward enlarge the realization category.  The resource is a temporary branch, subsystem, or borrowed state rather than a group element.
395 
396 \subsection{When defects are impossible}
397 A useful positive theorem is a criterion guaranteeing geodesic convexity.
398 \begin{proposition}[One-Lipschitz retraction criterion]
399 Suppose there is a group homomorphism $\pi:G\to H$ with $\pi|_H=\operatorname{id}_H$ such that every ambient generator $s\in\mathcal S_G$ satisfies
400 \[
401 \ell_H(\pi(s))\le c(s).
402 \]
403 Then
404 \[
405 \ell_H(h)\le\ell_G(h)
406 \]
407 for every $h\in H$, hence the two metrics agree on $H$.
408 \end{proposition}
409 \begin{proof}
410 For an ambient word $h=s_L\cdots s_1$, multiplicativity gives $h=\pi(h)=\pi(s_L)\cdots\pi(s_1)$.  Subadditivity and the generator bounds give $\ell_H(h)\le\sum_j c(s_j)$.  Taking the infimum over ambient words proves the claim.
411 \end{proof}
412 
413 The unitriangular counterexample proves that no such generator-wise one-Lipschitz retraction exists for the lower transvection model inside the all-transvection model.
414 
415 \subsection{Weighted restoration and phase transitions}
416 Let every restricted gate cost one and every ambient-only gate cost $\lambda$.  For a catalyst used by $v$ consumers with unit benefit, the displayed construction has net gain at least
417 \[
418 v-2\lambda.
419 \]
420 The critical weight is therefore target and mechanism dependent.
421 
422 \begin{definition}[Critical catalyst penalty]
423 For a target family $U_n$, define
424 \[
425 \lambda_c(U_n)
426 =
427 \sup\{\lambda:\ell_{\lambda,\mathrm{amb}}(U_n)<\ellRes(U_n)\}.
428 \]
429 \end{definition}
430 Determining $\lambda_c$ exactly is a refined synthesis problem.  It can be more physically meaningful than unweighted gate count.
431 
432 \subsection{Restoration is the source of nontriviality}
433 If the ambient resource need not be restored, the opening cost can dominate the comparison and many examples become trivial.  Catalytic escape is strongest when the following all hold:
434 \begin{enumerate}
435 \item the final target lies entirely in the restricted class,
436 \item every auxiliary subsystem or violated constraint is restored,
437 \item the ambient-only resource is used more than once,
438 \item the restricted lower bound charges the same repeated obligations separately,
439 \item the gain survives a realistic weighted cost.
440 \end{enumerate}
441 
442 \begin{conjecturebox}
443 In many finite gate hierarchies, minimal defects should admit a bounded-width catalytic normal form.  Proving or refuting this would turn an unrestricted synthesis search into a search over a finite family of excursion motifs.
444 \end{conjecturebox}
445 
446 \section{First arrival, spectral packets, algebraic rarity, and tensor regularization}\label{g:ch:spectral-algebraic}
447 \index{Green kernel}
448 \index{first-arrival valuation}
449 \index{word map}
450 \index{algebraic defect locus}
451 \index{border rank}
452 \index{tensor capacity}
453 
454 
455 \subsection{Word distance as first arrival}
456 Let $G$ be finite and let $S=S^{-1}$ be a symmetric generating multiset.  In the right regular representation, define
457 \[
458 A_S=\sum_{s\in S}\rho(s).
459 \]
460 Then
461 \[
462 \langle\delta_g,A_S^k\delta_e\rangle
463 \]
464 counts length-$k$ words ending at $g$.
465 
466 \begin{theorem}[Endpoint Green valuation]
467 The word distance is
468 \[
469 d_S(e,g)
470 =
471 \ord_{z=0}
472 \left\langle
473 \delta_g,(I-zA_S)^{-1}\delta_e
474 \right\rangle.
475 \]
476 \end{theorem}
477 \begin{proof}
478 Expand the resolvent as a formal power series:
479 \[
480 (I-zA_S)^{-1}=\sum_{k\ge0}z^kA_S^k.
481 \]
482 The first nonzero endpoint coefficient occurs at the shortest word length.
483 \end{proof}
484 
485 For strictly positive integer costs, replace each generator $s$ by the monomial $z^{c(s)}\rho(s)$.  Every coefficient then counts finitely many words of a given total cost, and the same formal inverse is defined.  Zero-cost cycles require separate treatment: they can create infinitely many words of cost zero, so the ordinary counting series need not exist.  The finite atlases with free gates use shortest-path search with zero-cost edges instead.  Multivariate variables can track several resources when the grading gives every generator positive total degree.
486 
487 \subsection{Why eigenvalues alone are insufficient}
488 If
489 \[
490 A_S=\sum_\lambda\lambda\Pi_\lambda,
491 \]
492 then
493 \[
494 \mathcal G_{S,g}(z)
495 =
496 \sum_\lambda
497 \frac{\langle\delta_g,\Pi_\lambda\delta_e\rangle}{1-\lambda z}.
498 \]
499 The eigenvalues and multiplicities do not determine the endpoint coefficients
500 \[
501 \langle\delta_g,\Pi_\lambda\delta_e\rangle.
502 \]
503 Two Cayley or Schreier systems can therefore be cospectral and still have different first-arrival behavior at distinguished targets.
504 
505 \begin{principle}[Embedded packet principle]
506 For threshold questions, a spectral label is usually weaker than an embedded spectral projector.  The matrix coefficients of the projector relative to the initial and target states retain positional information that multiplicities erase.
507 \end{principle}
508 
509 This distinction recurs in the Latin-square example discussed later.  The natural commuting row, column, and symbol operators have universal eigenvalue packets at fixed order, while the embedded incidence and transition data still vary.
510 
511 \subsection{Subgroup-holonomy Fourier packets}
512 Let $H\le G$.  Let $\mu_k(h)$ count ambient words of length $k$ with product $h\in H$.  For every irreducible representation $\tau\in\widehat H$, define
513 \[
514 \widehat\mu_k(\tau)
515 =
516 \sum_{h\in H}\mu_k(h)\tau(h).
517 \]
518 Fourier inversion gives
519 \[
520 \mu_k(h)
521 =
522 \frac1{|H|}
523 \sum_{\tau\in\widehat H}
524 \dim(\tau)
525 \operatorname{tr}
526 \bigl(
527 \tau(h^{-1})\widehat\mu_k(\tau)
528 \bigr).
529 \]
530 The matrix-valued Green packet
531 \[
532 \widehat{\mathcal G}_\tau(z)
533 =
534 \sum_{k\ge0}\widehat\mu_k(\tau)z^k
535 \]
536 recovers every endpoint series after Fourier inversion.
537 
538 The trivial representation records only the total number of loops returning to the subgroup.  Nontrivial $H$-types retain their holonomy.  This yields a hierarchy:
539 \[
540 \text{spherical return data}
541 \prec
542 \text{type-resolved holonomy packets}
543 \prec
544 \text{exact endpoint realization}.
545 \]
546 
547 \subsection{Word maps and product loci}
548 Let $K$ be a field and let $X\subseteq G$ be an algebraic gate family.  For a fixed length $L$, multiplication defines
549 \[
550 \mu_L:X^L\to G,
551 \qquad
552 (x_L,\ldots,x_1)\mapsto x_L\cdots x_1.
553 \]
554 The exact length-$L$ locus is $\mu_L(X^L)$, and the length-at-most-$L$ locus is a finite union of such images when the gate family has finitely many components.
555 
556 \begin{theorem}[Dimension per gate]
557 Suppose every irreducible component of $X$ has dimension at most $r$.  Then the Zariski closure of the locus reachable in at most $L$ gates has dimension at most $rL$.
558 \end{theorem}
559 \begin{proof}
560 Every component of $X^L$ has dimension at most $rL$.  A morphism cannot increase dimension.  A finite union has dimension equal to the maximum dimension of its components.
561 \end{proof}
562 
563 For scaled transvections, $r=1$.  This immediately yields generic lower bounds in a target variety whose dimension exceeds $L$.
564 
565 \subsection{Generic rigidity}
566 Work over an algebraically closed field.  Suppose the restricted target variety $V$ is irreducible of dimension $N$, every target has a restricted realization using at most $N$ unit-cost gates, and the ambient alphabet is an algebraic family with finitely many components of dimension at most one.  Then ambient realizations of length below $N$ occupy a proper closed subset of $V$.
567 
568 \begin{theorem}[Abstract generic rigidity]
569 Under the preceding hypotheses, there is a nonempty Zariski-open subset $\Omega\subseteq V$ such that
570 \[
571 \ellRes(U)=\ellAmb(U)=N
572 \qquad(U\in\Omega).
573 \]
574 \end{theorem}
575 The unitriangular theorem in the core chapter is a concrete instance with
576 \[
577 N=\binom n2.
578 \]
579 
580 \subsection{Defect codimension}
581 If every target has restricted cost at most $N$, then defect at least $d$ forces ambient cost at most $N-d$.  The dimension-per-gate theorem gives
582 \[
583 \codim_V\overline{\{U:\Delta(U)\ge d\}}
584 \ge d
585 \]
586 when each ambient gate carries one parameter.
587 
588 \begin{principle}[Rare but amplifiable]
589 At fixed dimension, large defects require increasingly special algebraic conditions.  Under direct sums, recursive lifts, or tensor products, a point on a thin exceptional stratum can nevertheless seed a macroscopic family.
590 \end{principle}
591 
592 This is one of the central tensions of the subject.  Catalysis is neither generic nor negligible.
593 
594 \subsection{Finite-field sparsity}
595 A word-counting analogue applies over $\F_q$.  If the ambient alphabet has at most $M(q-1)$ nontrivial scaled gates, then the number of targets reached in $L$ gates is at most
596 \[
597 \sum_{j=0}^L[M(q-1)]^j.
598 \]
599 When the target space has $q^N$ points and defect $d$ implies ambient length at most $N-d$, the crude bound is
600 \[
601 \Prob[\Delta\ge d]
602 =O_{N,M}(q^{-d}).
603 \]
604 The estimate can be sharpened by orbit counting, stabilizers, and the geometry of word-map fibers.
605 
606 \subsection{Direct sums and monoidal amplification}
607 Suppose targets admit a direct sum $U\oplus V$ and a homomorphism from the large restricted group onto the two factor groups sends $U\oplus V$ to $(U,V)$.  Require the aggregate generator bound
608 \[
609 \ellRes(\pi_1(s))+\ellRes(\pi_2(s))\le c(s)
610 \]
611 for every large restricted generator $s$.  Assume that both restricted and ambient factor circuits embed into the corresponding large model without increasing cost.  Then
612 \[
613 \ellRes(U\oplus V)
614 =
615 \ellRes(U)+\ellRes(V).
616 \]
617 Indeed, projecting any word and summing the two factor bounds gives the lower bound, while concatenating the embedded factor circuits gives the upper bound.  Separate one-Lipschitz projections alone do not imply this sum inequality.
618 Under the ambient embedding assumption, the constructive upper bound is
619 \[
620 \ellAmb(U\oplus V)
621 \le
622 \ellAmb(U)+\ellAmb(V),
623 \]
624 so
625 \[
626 \Delta(U\oplus V)
627 \ge
628 \Delta(U)+\Delta(V).
629 \]
630 One finite defect therefore gives an unbounded additive family.
631 
632 \subsection{Tensor products and normalized rates}
633 Let $U$ have dimension $m$ and $V$ dimension $n$.  In linear transvection models with tree-tight certificates,
634 \[
635 \ellRes(U\otimes V)
636 =
637 n\ellRes(U)+m\ellRes(V).
638 \]
639 The ambient model satisfies the corresponding inequality.  Normalizing by dimension gives an entropy-like law:
640 \[
641 \frac{\ellRes(U\otimes V)}{mn}
642 =
643 \frac{\ellRes(U)}m+
644 \frac{\ellRes(V)}n.
645 \]
646 The normalized defect is superadditive under tensor products.
647 
648 \begin{definition}[Tensor synergy]
649 Define
650 \[
651 \Syn(U,V)
652 =
653 n\ellAmb(U)+m\ellAmb(V)-\ellAmb(U\otimes V).
654 \]
655 Positive synergy means that the joint ambient realization improves on independent lifted circuits.
656 \end{definition}
657 Restricted tree-tight metrics have zero tensor synergy.  Ambient synergy is a possible source of collective activation.
658 
659 \begin{definition}[Stable tensor cost]
660 For a size-$m$ target $U$, define
661 \[
662 \tau_\otimes(U)
663 =
664 \lim_{r\to\infty}
665 \frac{\ellAmb(U^{\otimes r})}{r m^{r-1}},
666 \]
667 when the subadditivity argument applies.  Define
668 \[
669 \kappa_\otimes(U)
670 =
671 \ellRes(U)-\tau_\otimes(U).
672 \]
673 \end{definition}
674 Fekete's lemma gives the limit from the tensor subadditivity inequality.
675 
676 \begin{figure}[ht]
677 \centering
678 \includegraphics[width=.72\textwidth]{assets/g_tensor_capacity.pdf}
679 \caption{Schematic stable tensor capacity.  The figure illustrates definitions, not measured data.}
680 \end{figure}
681 
682 \begin{definition}[Tensor activation]
683 A target is tensor activated if
684 \[
685 \Delta(U)=0
686 \quad\text{but}\quad
687 \kappa_\otimes(U)>0.
688 \]
689 \end{definition}
690 This is analogous to regularized capacities and asymptotic ranks.  It asks whether collective synthesis can unlock a catalyst invisible in one copy.
691 
692 \subsection{Border catalysis}
693 Let $X_{\mathrm{res}}$ and $X_{\mathrm{amb}}$ be algebraic gate varieties.  The exact product rank is
694 \[
695 \operatorname{rk}_{X}(U)
696 =
697 \min\{L:U\in X^L\},
698 \]
699 while border product rank is
700 \[
701 \underline{\operatorname{rk}}_{X}(U)
702 =
703 \min\{L:U\in\overline{X^L}\}.
704 \]
705 The four possible comparisons are:
706 \begin{enumerate}
707 \item exact and border defects both positive,
708 \item exact defect positive but border defect zero,
709 \item one-copy defect zero but tensor-regularized defect positive,
710 \item ambient and restricted border ranks both smaller than exact ranks but by different amounts.
711 \end{enumerate}
712 Each requires a separate certificate.  Numerical approximation alone does not distinguish them.
713 
714 \subsection{A packet-resolved threshold principle}
715 Combining the preceding constructions gives the following architecture.
716 \begin{enumerate}
717 \item A coarse commutative algebra supplies spherical spectral packets.
718 \item Embedded projectors retain incidence and endpoint position.
719 \item Noncommutative transition data record holonomy.
720 \item A realization theorem decides whether the packet has a restricted representative and at what cost.
721 \item Direct sums and tensor products propagate local defects.
722 \end{enumerate}
723 
724 \begin{figure}[ht]
725 \centering
726 \includegraphics[width=.86\textwidth]{assets/g_packet_hierarchy.pdf}
727 \caption{The spectral-to-realization hierarchy.}
728 \label{g:fig:packet-hierarchy}
729 \end{figure}
730 
731 \begin{boundarybox}
732 A packet hierarchy organizes evidence.  It does not replace the final lower bound, positivity argument, orthogonality construction, or descent theorem.  Classification and realization remain distinct layers.
733 \end{boundarybox}
734 
735 \section{Matroidal state geometry, quiver factorizations, and root-system catalysis}\label{g:ch:matroid-quiver-roots}
736 \index{matroid}
737 \index{quiver}
738 \index{root system}
739 \index{Chevalley commutator}
740 \index{pattern group}
741 
742 
743 \subsection{Intermediate states as a representable matroid}
744 A linear circuit visits vectors that satisfy exact dependence relations.  If $\mathcal V$ is the set of all row states appearing during a computation, then $\mathcal V$ determines a representable matroid.  A transvection
745 \[
746 u\longmapsto u+a v
747 \]
748 creates a three-point projective line
749 \[
750 [u],\ [v],\ [u+av].
751 \]
752 The ambient circuit chooses a tour through this projective configuration.  A flag-preserving circuit must lift the same dependencies through prescribed pivot positions.
753 
754 \begin{definition}[Flagged matroid tour]
755 Let $M$ be a representable matroid with designated initial basis, target basis, and consumer states.  A \emph{flagged tour} is a sequence of basis exchanges or transvections in which the $i$th carrier remains inside a specified filtration layer.  An ambient tour drops this constraint.
756 \end{definition}
757 The six-row atom realizes the graphic regular matroid $M(K_4)$.  Its ambient state tour is shorter than every compatible flag lift.  Regularity explains why the same dependence pattern survives every field and, through integer matrices, every nonzero commutative coefficient ring in the stated model.
758 
759 \subsection{Matroidal classification problem}
760 The first general classification problem is:
761 \begin{quote}
762 Which regular matroids admit designated carrier and consumer roles for which an ambient tour is shorter than every flag-compatible tour?
763 \end{quote}
764 Natural subclasses are graphic, cographic, and network matrices.  Potential invariants include branch width, circuit size, excluded minors, and the number of consumer incidences supported by one projective line.
765 
766 \begin{conjecturebox}
767 Minimal field-universal catalytic atoms should be governed by regular matroids, while characteristic-dependent atoms should arise from representable matroids with excluded-characteristic minors.
768 \end{conjecturebox}
769 This conjecture is a programmatic guide.  The core paper establishes only the $M(K_4)$ instance.
770 
771 \subsection{Dynamic rank-one factorization}
772 Consider a height-two block shear
773 \[
774 E(C)=
775 \begin{pmatrix}
776 I_s&0\\
777 C&I_t
778 \end{pmatrix}.
779 \]
780 A restricted circuit may change source and output bases while transmitting rank-one terms.  Let $P_r\in U_s$ be the source basis before the $r$th transmission and let $Q_{>r}\in U_t$ be the future output basis.  A cross gate contributes
781 \[
782 Q_{>r}e_{i_r}e_{j_r}^{T}P_{<r}
783 \]
784 to the final block.  Hence
785 \[
786 C=
787 \sum_{r=1}^{c}
788 Q_{>r}e_{i_r}e_{j_r}^{T}P_{<r},
789 \]
790 with closed basis paths
791 \[
792 P_{\mathrm{final}}=I_s,
793 \qquad
794 Q_{\mathrm{final}}=I_t.
795 \]
796 
797 \begin{definition}[Dynamic rank-one cost]
798 The dynamic rank-one cost of $C$ is the minimum of
799 \[
800 \text{source basis motion}
801 +
802 \text{output basis motion}
803 +
804 \text{number of transmissions}
805 \]
806 over such timed decompositions.
807 \end{definition}
808 Ordinary rank retains only the number of transmissions after arbitrary bases are given for free.  Circuit complexity charges the closed paths needed to expose and restore those bases.
809 
810 \subsection{Quiver gate models}
811 Let $Q=(Q_0,Q_1)$ be a quiver.  Associate a vector space $V_v$ to every vertex.  Internal gates change bases inside $V_v$, while edge gates transmit low-rank maps along arrows.  A target is a representation of the path algebra or an automorphism of a filtered quiver module.
812 
813 This generalization includes:
814 \begin{itemize}
815 \item block-triangular linear circuits,
816 \item network coding with reversible local state,
817 \item layered dataflow architectures,
818 \item incidence-algebra transformations,
819 \item tensor networks with reusable bond states.
820 \end{itemize}
821 
822 A catalytic excursion can temporarily activate a forbidden arrow or enlarge a vertex space.  The restored target still lies in the original quiver representation class.
823 
824 \begin{skeletonbox}
825 A quiver threshold theorem should specify a forbidden-arrow motif, an exact ambient word, a projection-based restricted lower bound, and an amplification operation under quiver substitution.  The unitriangular snapshot family is the linearly ordered one-dimensional-vertex case.
826 \end{skeletonbox}
827 
828 \subsection{Pattern groups and architecture constraints}
829 For a poset $P$, define the pattern group
830 \[
831 U_P(K)
832 =
833 \{I+A:A_{ij}=0\text{ unless }j<_P i\}.
834 \]
835 When the allowed positions are transitively closed, $U_P$ is a group.  Compare the intrinsic metric generated by $P$-allowed transvections with the metric induced by all transvections.
836 
837 The first threshold now depends on the forbidden-edge geometry of $P$.  One may ask whether a six-role catalytic motif embeds as a generator-preserving retract.  If it does, the larger architecture inherits a defect.
838 
839 \begin{proposition}[Retraction inheritance]
840 Suppose a smaller nested pair $H\le G$ embeds into $H'\le G'$ by homomorphisms preserving the inclusion, the ambient embedding does not increase gate cost, and there is a homomorphic retraction $\pi:H'\to H$ onto the embedded copy.  Require $\ell_H(\pi(s))\le c(s)$ for every restricted generator $s$ of $H'$.  Then every defect in $H\le G$ gives a defect at least as large in $H'\le G'$.
841 \end{proposition}
842 The proof projects a restricted word in the larger system and embeds the shorter ambient word from the smaller system.
843 
844 \subsection{Root subgroups and Chevalley relations}
845 Let $G$ be a split reductive group \cite{g:Carter1972,g:Humphreys1975} with root system $\Phi$.  Let $\Psi\subseteq\Phi$ be a closed set of allowed roots and let $U_\Psi$ be generated by the root groups $x_\beta(t)$ for $\beta\in\Psi$.  Define
846 \[
847 \ell_\Psi(u)
848 =
849 \min\{L:u=x_{\beta_L}(t_L)\cdots x_{\beta_1}(t_1),\ \beta_i\in\Psi\},
850 \]
851 and let $\ell_\Phi$ permit all roots.
852 
853 The Chevalley conjugation formula has the schematic form
854 \[
855 x_\alpha(a)x_\beta(b)x_\alpha(a)^{-1}
856 =
857 x_\beta(b)
858 \prod_{k>0}
859 x_{\beta+k\alpha}(c_k a^k b).
860 \]
861 A forbidden root $\alpha$ can therefore create several allowed root effects before being removed.
862 
863 \begin{figure}[ht]
864 \centering
865 \includegraphics[width=.80\textwidth]{assets/g_root_catalysis.pdf}
866 \caption{A root-string template for catalytic generation.  Longer strings may support more gain per opening and closing pair.}
867 \end{figure}
868 
869 \subsection{Type \texorpdfstring{$A$}{A} and beyond}
870 Row transvections are root-group elements of type $A$.  The established unitriangular atom occurs in $A_5$.  In nonsimply laced systems, root strings can have length greater than two.  This raises the possibility that one ambient root can create multiple restricted effects per consumer.
871 
872 \begin{conjecture}[Long-root catalytic gain]
873 There exist gate alphabets in types $B$, $C$, or $G_2$ for which a clean one-catalyst multiplicative distortion exceeds the type-$A$ snapshot limit of $3/2$.
874 \end{conjecture}
875 No lower-bound certificate is presently supplied.  The conjecture identifies a concrete reason to test nonsimply laced root systems rather than merely repeating type $A$ computations.
876 
877 \subsection{Symplectic root systems and Clifford logic}
878 The binary Clifford group modulo phases acts through $\Sp(2n,2)$.  A parabolic subgroup stabilizing a Lagrangian is the symplectic analogue of a Borel or flag-preserving circuit class.  Hadamard gates leave this parabolic, while $S$, $\CZ$, and $\CX$ preserve it.  The exact Clifford censuses in \cref{g:ch:clifford} are therefore a first root-system extension of the linear theory.
879 
880 \subsection{Categorical realization defects}
881 The group framework does not cover measurement, feedforward, postselection, or entangled design objects.  Let
882 \[
883 \mathcal C_{\mathrm{res}}
884 \subseteq
885 \mathcal C_{\mathrm{amb}}
886 \]
887 be monoidal categories with costed generators.  A target morphism can have a finite metric defect or an infinite existence defect.
888 
889 The categorical viewpoint supports:
890 \begin{itemize}
891 \item unitary versus measurement-assisted circuits,
892 \item product-state versus entangled realizations,
893 \item clean versus borrowed ancilla categories,
894 \item symmetry-preserving versus symmetry-breaking channels,
895 \item exact versus approximate completion.
896 \end{itemize}
897 The common invariant is still the cost of a restored target.  What changes is the geometry of the path and the meaning of holonomy.
898 
899 \subsection{A general research dichotomy}
900 The broad program separates into two tasks.
901 \begin{enumerate}
902 \item \textbf{Construction:} exhibit an ambient excursion whose repeated consumers produce a cheaper target.
903 \item \textbf{Certification:} prove that the restricted category cannot share the same obligations as efficiently.
904 \end{enumerate}
905 Conjugation identities often solve the first task.  The second is the difficult part and requires model-specific invariants such as interval-tree rank, symplectic flag length, algebraic degree, phase-polynomial rank, covariance constraints, or branch complexity.
906 
907 \chapter{The complete linear core}
908 \section{Introduction}
909 
910 A CNOT circuit on $n$ labeled wires represents an element of $\GL_n(\F_2)=\SL_n(\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 \cite{g:SaeediMarkov2013,g:PatelMarkovHayes2008,g:JiangEtAl2020,g:GoubaultEtAl2021,g:Bataille2022,g:BuFanJoo2025,g:ChristensenEtAl2025,g:WebsterEtAl2025}.  Recent work has also produced stronger explicit lower-bound families and established NP-completeness of exact all-to-all CNOT distance \cite{g:Jorgensen2026,g:GongYu2026,g:AcuavivaEtAl2026}.  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.
911 
912 Let $R$ be a nonzero commutative ring with identity.  A row transvection is
913 \[
914 \tau_{t,s}(a)=I+aE_{t,s},
915 \qquad t\ne s,
916 \qquad a\in R\setminus\{0\},
917 \]
918 acting by
919 \[
920 R_t\longleftarrow R_t+aR_s.
921 \]
922 The transvection is \emph{lower directed} when $s<t$.  The lower-directed gates generate $\U_n(R)$.  We compare
923 \[
924 \ellDown(A)
925  =\min\{\text{number of lower-directed transvections producing }A\}
926 \]
927 with
928 \[
929 \ellAll(A)
930  =\min\{\text{number of arbitrary row transvections producing }A\},
931 \qquad A\in\U_n(R).
932 \]
933 For a field $\F$, the first metric is intrinsic to the unipotent radical and the second is induced from the elementary group $\Egrp_n(\F)=\SL_n(\F)$.
934 
935 The equality $\ellDown(A)=\ellAll(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 $\F_2$ and $\F_3$, and it is caused by a reusable temporary carrier rather than by a better ordering of the same lower gates.
936 
937 \subsection*{Main results}
938 
939 The first result is entirely analytic and does not require a field.
940 
941 \begin{theorem}[Universal catalytic atom over rings]\label{g:thm:universal-atom}
942 For every nonzero commutative ring $R$ with identity, let
943 \begin{equation}\label{g:eq:canonical-C}
944 C=
945 \begin{pmatrix}
946 1&0&0&0&0&0\\
947 1&1&0&0&0&0\\
948 0&0&1&0&0&0\\
949 0&1&1&1&0&0\\
950 1&1&1&0&1&0\\
951 1&1&1&0&0&1
952 \end{pmatrix}
953 \in\U_6(R).
954 \end{equation}
955 Then
956 \[
957 \ellDown(C)=7,
958 \qquad
959 \ellAll(C)=6.
960 \]
961 \end{theorem}
962 
963 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.
964 
965 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.
966 
967 \begin{theorem}[Exact binary threshold and census]\label{g:thm:binary-census}
968 Over $\F_2$:
969 \begin{enumerate}[label=\textup{(\roman*)}]
970 \item $\ellDown(A)=\ellAll(A)$ for every $A\in\U_n(\F_2)$ when $n\le5$.
971 \item Among the $2^{15}=32768$ matrices in $\U_6(\F_2)$, exactly twenty satisfy $\ellDown(A)>\ellAll(A)$.
972 \item Every defective target satisfies
973 \[
974 \ellDown(A)=7,
975 \qquad
976 \ellAll(A)=6.
977 \]
978 No other distance pair is defective.
979 \end{enumerate}
980 \end{theorem}
981 
982 The twenty targets have a uniform combinatorial explanation.
983 
984 \begin{theorem}[Minimal catalytic classification]\label{g:thm:motif-classification}
985 The twenty defective targets in $\U_6(\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
986 \[
987 6,
988 \qquad
989 8,
990 \qquad
991 6,
992 \]
993 for a total of twenty.
994 \end{theorem}
995 
996 The field-independent atom and exact ternary search also give the same finite threshold over $\F_3$.
997 
998 \begin{theorem}[Exact ternary threshold]\label{g:thm:ternary-threshold}
999 For $n\le5$ and every $A\in\U_n(\F_3)$,
1000 \[
1001 \ellDown(A)=\ellAll(A).
1002 \]
1003 The matrix $C\in\U_6(\F_3)$ of \cref{g:eq:canonical-C} has distances $(7,6)$.  Hence six is the first defective dimension over $\F_3$.
1004 \end{theorem}
1005 
1006 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.
1007 
1008 \begin{theorem}[Connected snapshot family]\label{g:thm:snapshot-family}
1009 Let $u\ge1$, let $1\le v\le u+1$, and choose distinct phases
1010 \[
1011 0\le s_1<\cdots<s_v\le u.
1012 \]
1013 There is a connected target
1014 \[
1015 A(u;s_1,\ldots,s_v)\in\U_{u+v+2}(\F)
1016 \]
1017 with
1018 \[
1019 \ellDown\bigl(A(u;s_1,\ldots,s_v)\bigr)=u+2v
1020 \]
1021 and
1022 \[
1023 \ellAll\bigl(A(u;s_1,\ldots,s_v)\bigr)\le u+v+2.
1024 \]
1025 Hence its certified defect is at least $v-2$.
1026 \end{theorem}
1027 
1028 \begin{corollary}[Connected defects in every dimension]\label{g:cor:connected-gap}
1029 For every field and every $n\ge7$, there is a connected target $A_n\in\U_n(\F)$ satisfying
1030 \[
1031 \ellDown(A_n)-\ellAll(A_n)
1032 \ge
1033 \left\lfloor\frac{n-5}{2}\right\rfloor.
1034 \]
1035 \end{corollary}
1036 
1037 The same construction remains effective under stringent restrictions on the ambient resource.
1038 
1039 \begin{theorem}[Two forbidden gates and weighted penalties]\label{g:thm:resource-robustness}
1040 For every field and every $n\ge7$, there is a connected target $A_n\in\U_n(\F)$ such that
1041 \[
1042 \ellBudget{0}(A_n)-\ellBudget{2}(A_n)
1043 \ge
1044 \left\lfloor\frac{n-5}{2}\right\rfloor,
1045 \]
1046 where $\ellBudget{q}$ permits at most $q$ upper-directed gates.  More generally, if lower gates have cost $1$ and upper gates have cost $\lambda>0$, then
1047 \[
1048 \ellDown(A_n)-\ellWeight{\lambda}(A_n)
1049 \ge
1050 \left\lfloor\frac{n-1}{2}\right\rfloor-2\lambda.
1051 \]
1052 Thus no fixed upper-gate budget of two, and no fixed finite upper-gate penalty, suppresses catalytic escape asymptotically.
1053 \end{theorem}
1054 
1055 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)=\rank X^+$, and let $b^+(X)$ be the largest upper displacement $j-i$ with $X_{ij}\ne0$.  If $\ellExc{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
1056 \[
1057 \ellExc{0}{0}(A_n)-\ellExc{1}{1}(A_n)
1058 \ge
1059 \left\lfloor\frac{n-5}{2}\right\rfloor.
1060 \]
1061 Thus a rank-one excursion across one adjacent flag layer can create a linear saving.
1062 
1063 At fixed dimension, however, defects occupy thin algebraic strata.
1064 
1065 \begin{theorem}[Generic rigidity and defect codimension]\label{g:thm:generic-rigidity-intro}
1066 Let $K$ be an infinite field and put $N=\binom n2$.  There is a nonempty Zariski-open subset $\Omega_n\subseteq\U_n$ with $\Omega_n(K)\ne\varnothing$ such that
1067 \[
1068 \ellDown(A)=\ellAll(A)=N
1069 \qquad(A\in\Omega_n(K)).
1070 \]
1071 Moreover, after base change to an algebraic closure $\overline K$, for
1072 \[
1073 \mathcal D_{n,\ge d}(\overline K)
1074 =\{A\in\U_n(\overline K):\DeltaDef(A)\ge d\},
1075 \]
1076 one has
1077 \[
1078 \codim_{(\U_n)_{\overline K}}
1079 \overline{\mathcal D_{n,\ge d}(\overline K)}\ge d.
1080 \]
1081 \end{theorem}
1082 
1083 \begin{corollary}[Finite-field sparsity]\label{g:cor:finite-field-sparsity-intro}
1084 Let $N=\binom n2$ and $M=n(n-1)$.  For $1\le d\le N$,
1085 \[
1086 \Prob_{A\in\U_n(\F_q)}[\DeltaDef(A)\ge d]
1087 \le
1088 \min\{1,M^{N-d}q^{-d}\}.
1089 \]
1090 For fixed $n$, a uniformly random target therefore has defect zero with probability $1-O_n(q^{-1})$ as $q\to\infty$.
1091 \end{corollary}
1092 
1093 Tensor products produce a stronger asymptotic separation.
1094 
1095 \begin{theorem}[Tensor-amplified snapshot family]\label{g:thm:tensor-main}
1096 Let $A=A(u;s_1,\ldots,s_v)$ have dimension $m=u+v+2$.  For $N=m^r$,
1097 \[
1098 \ellDown(A^{\otimes r})
1099 =r m^{r-1}(u+2v),
1100 \]
1101 while
1102 \[
1103 \ellAll(A^{\otimes r})
1104 \le r m^r.
1105 \]
1106 Consequently,
1107 \[
1108 \ellDown(A^{\otimes r})-\ellAll(A^{\otimes r})
1109 \ge
1110 \frac{v-2}{m\log_2m}N\log_2N.
1111 \]
1112 \end{theorem}
1113 
1114 \begin{corollary}[Explicit $n\log n$ distortion]\label{g:cor:nlogn-gap}
1115 For
1116 \[
1117 D_n(\F)
1118 =
1119 \sup_{A\in\U_n(\F)}
1120 \bigl(\ellDown(A)-\ellAll(A)\bigr),
1121 \]
1122 one has, for every field and every $n$,
1123 \[
1124 D_n(\F)
1125 \ge
1126 \frac{8}{21\log_2 21}n\log_2n
1127 -
1128 \frac{82}{105}n.
1129 \]
1130 The coefficient is attained within the snapshot family by the twenty-one-dimensional seed
1131 \[
1132 A(9;0,1,\ldots,9).
1133 \]
1134 \end{corollary}
1135 
1136 \subsection*{Conceptual interpretation}
1137 
1138 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.
1139 
1140 Over $\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.
1141 
1142 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.
1143 
1144 \subsection*{Scope}
1145 
1146 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.
1147 
1148 The paper is organized as follows.  \Cref{g:sec:model} fixes the circuit and metric conventions and gives the Schreier-holonomy interpretation.  \Cref{g:sec:atom} proves the universal ring-valued atom.  \Cref{g:sec:catalysis} develops the catalytic normal form and counts the twenty minimal motifs.  \Cref{g:sec:enumeration} gives the exact binary and ternary enumerations and proves the search procedure complete.  \Cref{g:sec:geometry-spectrum} gives the projective, regular-matroid, and Green-kernel formulations.  \Cref{g:sec:higher} develops interval-tree certificates, exact cases through dimension nine, and connected families in every larger dimension.  \Cref{g:sec:resources} proves bounded, weighted, and microscopic-excursion theorems.  \Cref{g:sec:rarity} proves generic rigidity, defect-codimension bounds, and finite-field sparsity.  \Cref{g:sec:amplification} 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.
1149 
1150 \subsection*{Proof and computation status}
1151 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.
1152 
1153 \section{Circuit model and metric comparison}\label{g:sec:model}
1154 
1155 \subsection{Transvections and row conventions}
1156 
1157 Fix a nonzero commutative ring $R$ with identity and an integer $n\ge2$.  Rows and columns are indexed by
1158 \[
1159 0,1,\ldots,n-1.
1160 \]
1161 For $s\ne t$ and $a\in R\setminus\{0\}$, set
1162 \[
1163 \tau_{t,s}(a)=I+aE_{t,s}.
1164 \]
1165 Left multiplication by $\tau_{t,s}(a)$ performs
1166 \[
1167 R_t\longleftarrow R_t+aR_s.
1168 \]
1169 We call $s$ the source and $t$ the target.  A circuit word
1170 \[
1171 w=(\tau_{t_m,s_m}(a_m),\ldots,\tau_{t_1,s_1}(a_1))
1172 \]
1173 produces
1174 \[
1175 [w]=\tau_{t_m,s_m}(a_m)\cdots\tau_{t_1,s_1}(a_1).
1176 \]
1177 
1178 Let
1179 \[
1180 S_n^\downarrow(R)
1181 =\{\tau_{t,s}(a):0\le s<t<n,\ a\in R\setminus\{0\}\}
1182 \]
1183 and
1184 \[
1185 S_n^*(R)
1186 =\{\tau_{t,s}(a):0\le s,t<n,\ s\ne t,\ a\in R\setminus\{0\}\}.
1187 \]
1188 Both sets are symmetric because
1189 \[
1190 \tau_{t,s}(a)^{-1}=\tau_{t,s}(-a).
1191 \]
1192 Let
1193 \[
1194 \Egrp_n(R)=\langle S_n^*(R)\rangle.
1195 \]
1196 When $R=\F$ is a field and $n\ge2$, elementary elimination gives
1197 \[
1198 \Egrp_n(\F)=\SL_n(\F).
1199 \]
1200 The ambient metric below is therefore the transvection word metric in $\SL_n(\F)$, viewed inside $\GL_n(\F)$.  When $\F=\F_2$, one has $\SL_n(\F_2)=\GL_n(\F_2)$, every generator is an involution, and it is exactly a CNOT gate under the usual row-action convention.
1201 
1202 \begin{lemma}\label{g:lem:lower-generates}
1203 The set $S_n^\downarrow(R)$ generates $\U_n(R)$.  Every prefix of a lower-directed circuit belongs to $\U_n(R)$.
1204 \end{lemma}
1205 
1206 \begin{proof}
1207 A lower-directed transvection is lower unitriangular, and products of lower-unitriangular matrices remain lower unitriangular.  Conversely, ordinary elimination of the strict lower entries, processed in a compatible order, expresses every element of $\U_n(R)$ as a product of lower-directed transvections.
1208 \end{proof}
1209 
1210 \begin{definition}[Intrinsic and ambient lengths]\label{g:def:lengths}
1211 For $A\in\U_n(R)$, define
1212 \[
1213 \ellDown(A)=|A|_{S_n^\downarrow(R)},
1214 \qquad
1215 \ellAll(A)=|A|_{S_n^*(R)}.
1216 \]
1217 The \emph{catalytic defect} is
1218 \[
1219 \DeltaDef(A)=\ellDown(A)-\ellAll(A)\ge0.
1220 \]
1221 \end{definition}
1222 
1223 The inequality follows because $S_n^\downarrow(R)\subseteq S_n^*(R)$.  The central question is whether the inclusion can be strict on a lower-unitriangular target.
1224 
1225 \subsection{Frame and flag interpretation}
1226 
1227 For the geometric interpretation in this subsection, assume $R=\F$ is a field.  An invertible matrix is an ordered basis
1228 \[
1229 (R_0,\ldots,R_{n-1})
1230 \]
1231 of $\F^n$.  A transvection replaces one basis vector by its sum with a nonzero multiple of another.  Let
1232 \[
1233 V_i=\Span(e_0,\ldots,e_i).
1234 \]
1235 A matrix lies in $\U_n(\F)$ exactly when
1236 \[
1237 R_i\in e_i+V_{i-1}
1238 \]
1239 for every $i$.  Thus lower circuits move among frames compatible with the standard complete flag
1240 \[
1241 V_0\subset V_1\subset\cdots\subset V_{n-1}.
1242 \]
1243 An upper-directed gate leaves this fiber of the flag map.  A strict defect means that the flag-compatible frame subgraph is not geodesically convex in the full transvection graph.
1244 
1245 \subsection{Schreier holonomy}
1246 
1247 Set
1248 \[
1249 G=\Egrp_n(R),
1250 \qquad
1251 H=\U_n(R).
1252 \]
1253 Consider the right Schreier graph on the left cosets $H\backslash G$: a generator $s\in S_n^*(R)$ gives an edge
1254 \[
1255 Hg\longrightarrow Hgs.
1256 \]
1257 A word representing $h\in H$ traces a based loop at the coset $H$.  Its label product is the holonomy $h$.
1258 
1259 \begin{proposition}[Holonomy-compression interpretation]\label{g:prop:schreier-holonomy}
1260 For $h\in H$, the ambient length $\ellAll(h)$ is the least length of a labeled based loop in $H\backslash G$ with holonomy $h$.  The restricted length $\ellDown(h)$ is the least length among such words whose every prefix remains in $H$.  Consequently,
1261 \[
1262 \DeltaDef(h)
1263 =
1264 \text{intrinsic flag-preserving cost}
1265 -
1266 \text{shortest ambient holonomy-loop cost}.
1267 \]
1268 \end{proposition}
1269 
1270 \begin{proof}
1271 A word $w=s_1\cdots s_k$ ends at the coset $Hw$.  It is a based loop exactly when $w\in H$, and its label product is then the represented element of $H$.  Minimizing over all transvection words representing $h$ gives $\ellAll(h)$.  Requiring every generator to be lower directed keeps every prefix in $H$ and gives $\ellDown(h)$.
1272 \end{proof}
1273 
1274 A catalytic shortcut is therefore a nonconstant quotient excursion whose accumulated holonomy is more expensive to produce inside the base fiber.
1275 
1276 \subsection{Two elementary counting lemmas}
1277 
1278 The proofs of the universal atom use only target counts and pivot support.
1279 
1280 \begin{lemma}[Target count]\label{g:lem:target-count}
1281 Suppose a circuit starts at the identity and finishes at $A$.
1282 \begin{enumerate}[label=\textup{(\roman*)}]
1283 \item If row $i$ of $A$ differs from $e_i$, then row $i$ is targeted at least once.
1284 \item If row $i$ of $A$ equals $e_i$ and is targeted, then it is targeted at least twice.
1285 \end{enumerate}
1286 \end{lemma}
1287 
1288 \begin{proof}
1289 A row changes only when it is targeted.  Every row of an invertible matrix over $R$ is unimodular.  If $aR_s=0$ for such a row, then multiplying a unimodular relation for $R_s$ by $a$ gives $a=0$.  Hence a gate with nonzero coefficient changes its target by a nonzero vector, so one targeting cannot leave that row equal to its initial value.
1290 \end{proof}
1291 
1292 \begin{lemma}[One-target source condition]\label{g:lem:one-target-source}
1293 Let $W\le R^n$.  Suppose row $t$ starts at $e_t$, is targeted exactly once, and finishes at
1294 \[
1295 e_t+w,
1296 \qquad w\in W,
1297 \]
1298 where at least one coordinate of $w$ is a unit of $R$.  At the moment of its unique targeting, the gate coefficient is a unit and the source row is a unit multiple of $w$.
1299 \end{lemma}
1300 
1301 \begin{proof}
1302 If the unique gate is $R_t\leftarrow R_t+aR_s$, then $aR_s=w$.  Choose a coordinate $j$ for which $w_j$ is a unit.  Since $a(R_s)_j=w_j$, the factor $a$ is a unit in the commutative ring $R$.  Hence $R_s=a^{-1}w$.
1303 \end{proof}
1304 
1305 The second lemma is especially restrictive when $W$ is a low-dimensional source space and output rows carry unique pivot coordinates outside $W$.
1306 
1307 \section{The universal six-row atom}\label{g:sec:atom}
1308 
1309 Let $R$ be a nonzero commutative ring with identity, and let
1310 \[
1311 v=e_1+e_2,
1312 \qquad
1313 w=e_0+e_1+e_2,
1314 \qquad
1315 W=\Span(e_0,e_1,e_2).
1316 \]
1317 The target $C$ of \cref{g:eq:canonical-C} has rows
1318 \begin{align*}
1319 R_0&=e_0,
1320 & R_1&=e_1+e_0,
1321 & R_2&=e_2,\\
1322 R_3&=e_3+v,
1323 & R_4&=e_4+w,
1324 & R_5&=e_5+w.
1325 \end{align*}
1326 
1327 \begin{figure}[t]
1328 \centering
1329 \includegraphics[width=.56\linewidth]{assets/g_canonical_matrix.pdf}
1330 \caption{The canonical target $C$.  Black cells are nonzero.  Rows $0$ and $2$ are restored exactly, while rows $3,4,5$ require two distinct additions $v$ and $w$ from the source space $W$.}
1331 \label{g:fig:canonical-matrix}
1332 \end{figure}
1333 
1334 \subsection{A six-gate ambient word}
1335 
1336 \begin{proposition}\label{g:prop:ambient-upper}
1337 For every nonzero commutative ring $R$ with identity,
1338 \[
1339 \ellAll(C)\le6.
1340 \]
1341 \end{proposition}
1342 
1343 \begin{proof}
1344 Apply the following six gates:
1345 \begin{align}
1346 R_1&\leftarrow R_1+R_2,\label{g:gate:a1}\\
1347 R_3&\leftarrow R_3+R_1,\label{g:gate:a2}\\
1348 R_1&\leftarrow R_1+R_0,\label{g:gate:a3}\\
1349 R_4&\leftarrow R_4+R_1,\label{g:gate:a4}\\
1350 R_5&\leftarrow R_5+R_1,\label{g:gate:a5}\\
1351 R_1&\leftarrow R_1-R_2.\label{g:gate:a6}
1352 \end{align}
1353 After \cref{g:gate:a1}, row $1$ contains $v$.  Gate \cref{g:gate:a2} copies $v$ to row $3$.  Gate \cref{g:gate:a3} changes the carrier to $w$, which is copied to rows $4$ and $5$ by \cref{g:gate:a4,g:gate:a5}.  Gate \cref{g:gate:a6} removes the temporary $e_2$ component, leaving $e_1+e_0$.  Every row now agrees with $C$.
1354 \end{proof}
1355 
1356 \begin{figure}[t]
1357 \centering
1358 \includegraphics[width=.98\linewidth]{assets/g_carrier_timeline.pdf}
1359 \caption{Carrier timeline for the six-gate ambient word.  The two upper-directed operations are the opening and closing gates on row $1$.  The state $e_1+e_2$ is exported once and $e_0+e_1+e_2$ is exported twice.}
1360 \label{g:fig:carrier-timeline}
1361 \end{figure}
1362 
1363 \subsection{A seven-gate lower word}
1364 
1365 \begin{proposition}\label{g:prop:lower-upper}
1366 For every nonzero commutative ring $R$ with identity,
1367 \[
1368 \ellDown(C)\le7.
1369 \]
1370 \end{proposition}
1371 
1372 \begin{proof}
1373 The lower-directed word
1374 \begin{align*}
1375 R_1&\leftarrow R_1+R_0,\\
1376 R_2&\leftarrow R_2+R_1,\\
1377 R_3&\leftarrow R_3-R_0,\\
1378 R_3&\leftarrow R_3+R_2,\\
1379 R_4&\leftarrow R_4+R_2,\\
1380 R_5&\leftarrow R_5+R_2,\\
1381 R_2&\leftarrow R_2-R_1
1382 \end{align*}
1383 produces $C$.  After the first two gates, row $2$ contains $w$.  Rows $4$ and $5$ copy that state.  The two gates on row $3$ cancel the unwanted $e_0$ and leave $v$.  The final gate restores row $2$.
1384 \end{proof}
1385 
1386 \subsection{Restricted lower bound}
1387 
1388 \begin{proposition}\label{g:prop:lower-lower-bound}
1389 For every nonzero commutative ring $R$ with identity,
1390 \[
1391 \ellDown(C)\ge7.
1392 \]
1393 \end{proposition}
1394 
1395 \begin{proof}
1396 Rows $1,3,4,5$ differ from their initial values, so they must each be targeted.  Assume for contradiction that a lower-directed word of length at most six produces $C$.
1397 
1398 First suppose row $2$ is never targeted.  Row $0$ remains $e_0$, row $2$ remains $e_2$, and every state ever assumed by row $1$ lies in $\Span(e_0,e_1)$ because the only possible source below row $1$ is row $0$.  Every output row retains coefficient $1$ on its own pivot coordinate in a lower-directed circuit, so no output row can lie in $W$.  Hence no available source row is a unit multiple of either
1399 \[
1400 v=e_1+e_2
1401 \quad\text{or}\quad
1402 w=e_0+e_1+e_2.
1403 \]
1404 By \cref{g:lem:one-target-source}, each of rows $3,4,5$ must be targeted at least twice.  Together with the required targeting of row $1$, this gives at least seven gates.
1405 
1406 Now suppose row $2$ is targeted.  Since its final value is $e_2$, \cref{g:lem:target-count} forces at least two targetings of row $2$.  A six-gate word must therefore target row $2$ exactly twice and each of rows $1,3,4,5$ exactly once.  Each output row $3,4,5$ must receive its complete addition in its unique targeting.  Row $0$ cannot supply $v$ or $w$, and row $1$ never contains an $e_2$ component.  Therefore row $2$ must supply all three outputs, up to unit scaling.  But two targetings of row $2$ expose at most one noninitial intermediate state before row $2$ returns to $e_2$, while the outputs require both distinct states $v$ and $w$.  This is impossible.
1407 \end{proof}
1408 
1409 \subsection{Ambient lower bound}
1410 
1411 \begin{proposition}\label{g:prop:ambient-lower-bound}
1412 For every nonzero commutative ring $R$ with identity,
1413 \[
1414 \ellAll(C)\ge6.
1415 \]
1416 \end{proposition}
1417 
1418 \begin{proof}
1419 Assume that an ambient word of length at most five produces $C$.  Rows $1,3,4,5$ must each be targeted.  Rows $0$ and $2$ are unchanged.  If either were targeted, it would require at least two targetings, giving at least six gates in total.  Thus rows $0$ and $2$ are never targeted.  If all four changed rows are targeted once, each has only its initial and final state.  No such source is a unit multiple of $v=e_1+e_2$ or $w=e_0+e_1+e_2$, so the output rows cannot be completed.  In the only remaining case, exactly one of rows $1,3,4,5$ is targeted twice and the other three are targeted once.
1420 
1421 Project the rows to the quotient module $R^6/W$.  Rows $0,1,2$ have zero image, while rows $3,4,5$ begin and end at the three distinct quotient basis vectors of the free quotient module.  An output row targeted exactly once must therefore use a source lying in $W$, by \cref{g:lem:one-target-source}.
1422 
1423 Suppose first that row $1$ is the twice-targeted row.  The three output rows are each targeted once.  Rows $0$ and $2$ supply only scalar multiples of $e_0$ and $e_2$.  Row $1$ begins at $e_1$, has one intermediate state, and ends at $e_1+e_0$.  Thus at most one of the two required unit-multiple classes of $v$ and $w$ can appear as an available source.  The three outputs require both, a contradiction.
1424 
1425 Suppose instead that an output row, say row $r\in\{3,4,5\}$, is targeted twice.  The other two outputs and row $1$ are targeted once.  We claim that row $r$ cannot lie in $W$ between its two targetings.  To cancel its unique quotient pivot $e_r$ at the first targeting, the source would already have to contain an $e_r$ component.  Before row $r$ is first targeted, the only way another row can acquire such a component is to be targeted using row $r$ as source.  That other row is targeted only once and would then retain an unwanted $e_r$ component in its final value.  Therefore row $r$ never becomes a $W$-valued carrier.  The only $W$-valued source states are rows $0$ and $2$ and the two states of singly targeted row $1$, namely its initial and final states.  None supplies both $v$ and $w$.  The two singly targeted outputs cannot be completed, again a contradiction.
1426 \end{proof}
1427 
1428 \begin{proof}[Proof of \cref{g:thm:universal-atom}]
1429 Combine \cref{g:prop:ambient-upper,g:prop:lower-upper,g:prop:lower-lower-bound,g:prop:ambient-lower-bound}.
1430 \end{proof}
1431 
1432 \begin{remark}
1433 The proof uses only unimodular rows, unit coordinates, and pivot support.  It does not use division or a characteristic assumption.  In characteristic two the closing subtraction equals addition.
1434 \end{remark}
1435 
1436 \begin{corollary}[Failure of geodesic convexity]\label{g:cor:nonconvex}
1437 For every field $\F$ and every $n\ge6$, the lower-unitriangular frame subgraph is not geodesically convex in the transvection Cayley graph of $\Egrp_n(\F)=\SL_n(\F)$.
1438 \end{corollary}
1439 
1440 \begin{proof}
1441 Embed $C$ as $C\oplus I_{n-6}$.  A six-gate ambient word acts on the first six rows.  In a lower-directed circuit, rows with index at least six cannot be used as sources for targets among the first six rows, so the restricted lower bound of seven persists.
1442 \end{proof}
1443 
1444 For the remainder of the paper, unless explicitly stated otherwise, the coefficient domain is a field $\F$.
1445 
1446 \section{Catalytic normal forms and the six-role threshold}\label{g:sec:catalysis}
1447 
1448 The universal atom is one instance of a root-conjugation mechanism.  This section isolates that mechanism and explains the count twenty.
1449 
1450 \subsection{Root conjugation identities}
1451 
1452 Let $p<q<y$ and $x<p<q$.  Direct multiplication gives
1453 \begin{equation}\label{g:eq:read-conjugation}
1454 \tau_{p,q}(-a)\,\tau_{y,p}(b)\,\tau_{p,q}(a)
1455 =
1456 \tau_{y,p}(b)\,\tau_{y,q}(ab),
1457 \end{equation}
1458 and
1459 \begin{equation}\label{g:eq:update-conjugation}
1460 \tau_{p,q}(-a)\,\tau_{q,x}(b)\,\tau_{p,q}(a)
1461 =
1462 \tau_{q,x}(b)\,\tau_{p,x}(-ab).
1463 \end{equation}
1464 A single forbidden upper transvection can therefore turn one lower interaction into two lower effects.  Interactions of the forms $x\to p$ and $q\to y$ commute through the excursion without duplication.  We call the duplicated interactions \emph{cross interactions} and the unduplicated interactions \emph{phase interactions}.
1465 
1466 \begin{definition}[Simple one-catalyst word]\label{g:def:simple-catalyst}
1467 A simple one-catalyst word has the form
1468 \[
1469 \tau_{p,q}(-a)\,h_m\cdots h_1\,\tau_{p,q}(a),
1470 \qquad p<q,
1471 \]
1472 where every $h_i$ is lower directed and is one of
1473 \[
1474 \tau_{q,x}(b),\quad \tau_{p,x}(b),\quad
1475 \tau_{y,p}(b),\quad \tau_{y,q}(b)
1476 \]
1477 with $x<p<q<y$.  Auxiliary rows are distinct unless stated otherwise.
1478 \end{definition}
1479 
1480 The circuit is read from right to left in the matrix product and from left to right as a gate list.  The opening and closing operations temporarily place the $q$ component in row $p$.
1481 
1482 \begin{proposition}[Cross-interaction accounting]\label{g:prop:cross-accounting}
1483 Let a simple one-catalyst word have $m$ middle interactions, of which $c$ are cross interactions.  Its target admits a lower-directed realization of length at most
1484 \[
1485 m+c.
1486 \]
1487 Consequently, if the ambient word of length $m+2$ is strictly shorter than every lower word, then
1488 \[
1489 c\ge3.
1490 \]
1491 \end{proposition}
1492 
1493 \begin{proof}
1494 Conjugate each middle generator using \cref{g:eq:read-conjugation,g:eq:update-conjugation}.  A phase interaction remains one lower transvection, while a cross interaction becomes a product of two lower transvections.  This gives length at most $m+c$.  If $c\le2$, then $m+c\le m+2$, so the ambient excursion cannot be strictly better.
1495 \end{proof}
1496 
1497 Three consumers are therefore the first possible point at which the cost two of opening and closing can be amortized.
1498 
1499 \subsection{Why an all-cross word is insufficient}
1500 
1501 Within the distinct-leaf normal form, cross count alone is not enough.
1502 
1503 \begin{lemma}[All-cross mirror]\label{g:lem:all-cross-mirror}
1504 Suppose a simple one-catalyst word contains only cross interactions, with left inputs $X$ and right outputs $Y$.  Then its target has a lower-directed realization with the same number of gates.
1505 \end{lemma}
1506 
1507 \begin{proof}
1508 Write the opening coefficient as $a\in\F^\times$, the left-update coefficients as $b_x$, and the right-read coefficients as $c_y$.  Since the all-cross middle gates commute past one another, the ambient gate list may be written
1509 \[
1510 R_p\leftarrow R_p+aR_q;
1511 \quad
1512 [R_q\leftarrow R_q+b_xR_x]_{x\in X};
1513 \quad
1514 [R_y\leftarrow R_y+c_yR_p]_{y\in Y};
1515 \quad
1516 R_p\leftarrow R_p-aR_q.
1517 \]
1518 Put $B=\sum_{x\in X}b_xe_x$.  Its final nontrivial rows are
1519 \[
1520 R_p=e_p-aB,
1521 \qquad
1522 R_q=e_q+B,
1523 \qquad
1524 R_y=e_y+c_ye_p+ac_ye_q
1525 \quad(y\in Y).
1526 \]
1527 The following lower-directed gate list produces the same rows:
1528 \[
1529 R_q\leftarrow R_q+a^{-1}R_p;
1530 \quad
1531 [R_y\leftarrow R_y+ac_yR_q]_{y\in Y};
1532 \quad
1533 [R_p\leftarrow R_p-ab_xR_x]_{x\in X};
1534 \quad
1535 R_q\leftarrow R_q-a^{-1}R_p.
1536 \]
1537 Indeed, after the first gate $R_q=e_q+a^{-1}e_p$, so the output gates create exactly $c_ye_p+ac_ye_q$.  The source updates then leave $R_p=e_p-aB$, and the final gate changes $R_q$ to $e_q+B$.  Both words have $|X|+|Y|+2$ gates.
1538 \end{proof}
1539 
1540 Thus a minimal strict shortcut needs both positive catalytic excess and a phase switch that makes temporal order matter.
1541 
1542 \begin{proposition}[Six-role threshold in the simple model]\label{g:prop:six-role}
1543 A strict shortcut in the distinct-leaf simple one-catalyst model requires at least six row roles:
1544 \[
1545 2\text{ catalyst rows}
1546 +
1547 3\text{ cross interactions}
1548 +
1549 1\text{ phase interaction}.
1550 \]
1551 The bound is attained by the matrix $C$.
1552 \end{proposition}
1553 
1554 \begin{proof}
1555 By \cref{g:prop:cross-accounting}, at least three cross interactions are required.  By \cref{g:lem:all-cross-mirror}, at least one phase interaction is required.  With distinct leaves these use four auxiliary rows in addition to the two catalyst rows.  The word of \cref{g:prop:ambient-upper} has exactly this form.
1556 \end{proof}
1557 
1558 \begin{figure}[t]
1559 \centering
1560 \includegraphics[width=.82\linewidth]{assets/g_catalytic_motif.pdf}
1561 \caption{The minimal one-catalyst motif.  Cross interactions reuse the opened carrier.  The phase gate separates consumers that observe two different carrier states and prevents the all-cross mirror.}
1562 \label{g:fig:catalytic-motif}
1563 \end{figure}
1564 
1565 \subsection{Enumeration of the minimal motifs}
1566 
1567 Fix six ordered rows.  The catalyst pair must be adjacent in a minimal six-role word.  Write
1568 \[
1569 p<q=p+1,
1570 \]
1571 let $L$ be the set of rows left of $p$, and let $R$ be the set of rows right of $q$.  Then
1572 \[
1573 |L|+|R|=4,
1574 \qquad
1575 |L|,|R|>0.
1576 \]
1577 There are two orientations.
1578 
1579 \paragraph{Left phase.}
1580 Choose a phase leaf $x\in L$.  The remaining $|L|-1$ left leaves interact by $u\to q$.  Every right leaf is a cross read $p\to y$.  To make the phase effective, the right leaves are divided into a nonempty set read before $x\to p$ and a nonempty set read after it.  The number of targets is
1581 \[
1582 |L|\bigl(2^{|R|}-2\bigr).
1583 \]
1584 
1585 \paragraph{Right phase.}
1586 Choose a phase leaf $y\in R$.  Every other right leaf is a cross read.  The left updates into $q$ are divided nontrivially before and after the phase gate $q\to y$.  The number is
1587 \[
1588 |R|\bigl(2^{|L|}-2\bigr).
1589 \]
1590 
1591 \begin{proposition}[Motif count]\label{g:prop:motif-count}
1592 For a split $(L,R)=(|L|,|R|)$ with $L+R=4$, the number of minimal phase-separated targets is
1593 \[
1594 N_{L,R}
1595 =L(2^R-2)+R(2^L-2).
1596 \]
1597 For the three possible splits,
1598 \[
1599 N_{1,3}=6,
1600 \qquad
1601 N_{2,2}=8,
1602 \qquad
1603 N_{3,1}=6.
1604 \]
1605 Hence there are twenty targets.
1606 \end{proposition}
1607 
1608 \begin{proof}
1609 The preceding left-phase and right-phase constructions are disjoint because the phase row lies on opposite sides of the catalyst.  Within each orientation, the final support records the phase leaf and the before/after subset, so distinct choices give distinct targets.  Summing gives the formula and the stated values.
1610 \end{proof}
1611 
1612 \begin{figure}[t]
1613 \centering
1614 \includegraphics[width=.70\linewidth]{assets/g_motif_count.pdf}
1615 \caption{The analytic count of the twenty minimal catalytic targets.}
1616 \label{g:fig:motif-count}
1617 \end{figure}
1618 
1619 Every target counted by \cref{g:prop:motif-count} has an explicit six-gate ambient word and a seven-gate lower word obtained by eliminating the three cross interactions.  The nontrivial statement is that there are no other defects in dimension six and that none of these targets has a lower word of length six.  That is the exact classification established in \cref{g:sec:enumeration}.
1620 
1621 \section{Exact finite enumeration}\label{g:sec:enumeration}
1622 
1623 This section describes the computer-assisted part of the paper.  The computations use integer encodings only.  No floating-point decisions occur.
1624 
1625 \subsection{Restricted breadth-first search}
1626 
1627 Over $\F_2$, an element of $\U_n(\F_2)$ is determined by its $n(n-1)/2$ strict lower entries.  For $n=6$ there are $2^{15}=32768$ states.  Breadth-first search from the identity using the fifteen lower transvections gives every restricted distance and the restricted diameter.
1628 
1629 For $n=6$, the restricted diameter is eight.  Therefore every lower-unitriangular target has ambient distance at most eight.  This makes a radius-four meet-in-the-middle search complete.
1630 
1631 \subsection{Ambient radius-four ball and right-coset pairing}
1632 
1633 Let
1634 \[
1635 B_4=\{g\in\GL_6(\F_2):\ellAll(g)\le4\}.
1636 \]
1637 Exact breadth-first search gives
1638 \[
1639 |B_4|=110626.
1640 \]
1641 Group $B_4$ by right cosets of $\U_6(\F_2)$.  If $a,b$ lie in the same right coset, then
1642 \[
1643 b^{-1}a\in\U_6(\F_2),
1644 \]
1645 and
1646 \[
1647 \ellAll(b^{-1}a)\le\ellAll(b)+\ellAll(a)\le8.
1648 \]
1649 The implementation uses a canonical right-coset key obtained by reducing matrix columns from right to left.  Right multiplication by a lower-unitriangular matrix changes column $j$ only by a combination of columns with larger index, so this reduction is constant on right cosets and separates them.
1650 
1651 \begin{lemma}[Meet-in-the-middle completeness]\label{g:lem:mitm-complete}
1652 For every $u\in\U_6(\F_2)$,
1653 \[
1654 \ellAll(u)
1655 =
1656 \min\{\ellAll(a)+\ellAll(b):a,b\in B_4,\ b^{-1}a=u\}.
1657 \]
1658 \end{lemma}
1659 
1660 \begin{proof}
1661 Every pair on the right gives a word for $u$, so the right-hand side is at least $\ellAll(u)$.  Conversely, $\ellAll(u)\le8$.  Take a shortest path from the identity to $u$ and split it at a midpoint.  The prefix endpoint $a$ has distance at most four.  The inverse of the remaining suffix is an element $b$ of distance at most four, and $u=b^{-1}a$.  Hence the minimum is at most $\ellAll(u)$.
1662 \end{proof}
1663 
1664 The radius-four ball splits into $6948$ right-coset buckets.  The largest bucket has $3775$ elements.  The computation checks $45178326$ ordered pairs and recovers an ambient distance for every one of the $32768$ targets.
1665 
1666 \subsection{The exact binary census}
1667 
1668 \begin{table}[t]
1669 \centering
1670 \caption{Complete distance distribution in $\U_6(\F_2)$.}
1671 \label{g:tab:census}
1672 \begin{tabular}{@{}rrr@{}}
1673 \toprule
1674 $\ellDown$ & $\ellAll$ & number of targets\\
1675 \midrule
1676 0&0&1\\
1677 1&1&15\\
1678 2&2&125\\
1679 3&3&720\\
1680 4&4&2914\\
1681 5&5&7851\\
1682 6&6&12656\\
1683 7&6&20\\
1684 7&7&7926\\
1685 8&8&540\\
1686 \bottomrule
1687 \end{tabular}
1688 \end{table}
1689 
1690 \begin{figure}[t]
1691 \centering
1692 \includegraphics[width=.72\linewidth]{assets/g_distance_census.pdf}
1693 \caption{Complete binary dimension-six census.  The only off-diagonal cell contains the twenty targets with distance pair $(7,6)$.}
1694 \label{g:fig:distance-census}
1695 \end{figure}
1696 
1697 \begin{proof}[Proof of \cref{g:thm:binary-census}]
1698 For $n=2,3,4,5$, complete restricted breadth-first search and complete ambient meet-in-the-middle search return zero defects.  The state counts are respectively $2,8,64,1024$.  For $n=6$, \cref{g:lem:mitm-complete} proves that the ambient calculation is exhaustive.  The resulting distribution is \cref{g:tab:census}; its counts sum to $32768$, no target is missing, and the only strict pair is $(7,6)$ with multiplicity twenty.
1699 \end{proof}
1700 
1701 \begin{proof}[Proof of \cref{g:thm:motif-classification}]
1702 The analytic generator of \cref{g:prop:motif-count} produces twenty distinct targets without reference to the distance census.  Exact set comparison shows that these twenty targets are precisely the twenty off-diagonal targets in \cref{g:tab:census}.  Each therefore has distances $(7,6)$, and no other dimension-six target is defective.
1703 \end{proof}
1704 
1705 \subsection{Ternary and additional field checks}
1706 
1707 For $\F_3$, every nonzero scaled transvection is included.  Complete searches give the data in \cref{g:tab:small-fields}.
1708 
1709 \begin{table}[t]
1710 \centering
1711 \caption{Complete no-defect computations below dimension six.}
1712 \label{g:tab:small-fields}
1713 \begin{tabular}{@{}crrr@{}}
1714 \toprule
1715 field & $n$ & $|\U_n(\F)|$ & restricted diameter\\
1716 \midrule
1717 $\F_2$&2&2&1\\
1718 $\F_2$&3&8&2\\
1719 $\F_2$&4&64&4\\
1720 $\F_2$&5&1024&6\\
1721 \addlinespace
1722 $\F_3$&2&3&1\\
1723 $\F_3$&3&27&3\\
1724 $\F_3$&4&729&5\\
1725 $\F_3$&5&59049&7\\
1726 \bottomrule
1727 \end{tabular}
1728 \end{table}
1729 
1730 The $n=5$ ternary computation uses radius-three and radius-four balls, checks $38415205$ right-coset pairs, and recovers all $59049$ targets.  It finds no defect.  The field-independent \cref{g:thm:universal-atom} supplies a defect at $n=6$, proving \cref{g:thm:ternary-threshold}.  Separate exact searches over $\F_3$ and $\F_5$ verify the distances of the canonical atom directly.  The $\F_5$ calculation is an audit of the atom, not a complete threshold computation below dimension six.
1731 
1732 \subsection{Verification status}
1733 
1734 The analytic proofs of \cref{g:thm:universal-atom,g:cor:linear-gap} do not depend on computation.  The claims in \cref{g:thm:binary-census,g:thm:motif-classification,g:thm:ternary-threshold} depend on exact finite enumeration.  The source archive contains:
1735 \begin{itemize}
1736 \item the C++ programs for every breadth-first and meet-in-the-middle search;
1737 \item the Python program that independently generates the twenty motifs and compares sets;
1738 \item symbolic checks for the bounded-resource formulas and the totally unimodular $M(K_4)$ representation;
1739 \item exact stdout files and JSON packet data;
1740 \item SHA-256 checksums;
1741 \item build and reproduction commands.
1742 \end{itemize}
1743 The programs were rebuilt from source and rerun independently when this manuscript was assembled; the outputs matched byte for byte.
1744 
1745 \section{Projective, matroidal, and spectral structure}\label{g:sec:geometry-spectrum}
1746 
1747 \subsection{The flagged Pasch packet}
1748 
1749 Over $\F_2$, write
1750 \[
1751 x=e_0,
1752 \qquad
1753 p=e_1,
1754 \qquad
1755 q=e_2.
1756 \]
1757 The canonical ambient word uses the six nonzero vectors
1758 \[
1759 x,
1760 \quad p,
1761 \quad q,
1762 \quad p+q,
1763 \quad p+q+x,
1764 \quad p+x
1765 \]
1766 inside $\Span(x,p,q)\cong\F_2^3$.  The only missing nonzero vector is $x+q$.
1767 
1768 In $\operatorname{PG}(2,2)$, three distinct points form a line exactly when their vector representatives sum to zero.  The six points support the four lines
1769 \[
1770 \{x,p,x+p\},
1771 \quad
1772 \{x,p+q,x+p+q\},
1773 \quad
1774 \{p,q,p+q\},
1775 \quad
1776 \{x+p,q,x+p+q\}.
1777 \]
1778 Every point lies on exactly two of these lines.  This is the Pasch configuration, equivalently the Fano plane with one point and its three incident lines removed from the full incidence structure.
1779 
1780 \begin{figure}[t]
1781 \centering
1782 \includegraphics[width=.65\linewidth]{assets/g_pasch_configuration.pdf}
1783 \caption{A real drawing of the four-line Pasch incidence structure.  The labels are the binary point encodings $1,2,3,4,6,7$; point $5$ is the missing Fano point.}
1784 \label{g:fig:pasch}
1785 \end{figure}
1786 
1787 The configuration is flagged because the rows have fixed roles.  Points $x$ and $q$ are stationary sources, $p$ is the carrier, and the remaining points occur as carrier states.  Forgetting those roles loses the circuit ordering information.
1788 
1789 \subsection{The regular matroid \texorpdfstring{$M(K_4)$}{M(K4)}}
1790 
1791 The six carrier states admit a field-independent representation.  In the ordered basis $(x,p,q)$, place them as the columns of
1792 \begin{equation}\label{g:eq:k4-matrix}
1793 B=
1794 \begin{pmatrix}
1795 1&0&0&1&0&1\\
1796 0&1&0&1&1&1\\
1797 0&0&1&0&1&1
1798 \end{pmatrix},
1799 \end{equation}
1800 corresponding respectively to
1801 \[
1802 x,
1803 \quad p,
1804 \quad q,
1805 \quad x+p,
1806 \quad p+q,
1807 \quad x+p+q.
1808 \]
1809 
1810 \begin{proposition}[Regular-matroid core]\label{g:prop:regular-matroid}
1811 Every square minor of $B$ belongs to $\{0,\pm1\}$, so $B$ is totally unimodular.  Hence the column-dependence matroid is the same over every field.  Under the edge labeling
1812 \[
1813 \begin{array}{c|cccccc}
1814 \text{state}&p&x&x+p&p+q&q&x+p+q\\
1815 \hline
1816 K_4\text{ edge}&12&13&23&14&24&34,
1817 \end{array}
1818 \]
1819 it is the graphic matroid $M(K_4)$.
1820 \end{proposition}
1821 
1822 \begin{proof}
1823 A direct calculation of all square minors of $B$ gives only $0$, $1$, and $-1$.  Thus every subdeterminant has characteristic-independent vanishing, and a column set is independent over one field exactly when it is independent over every field.  The four minimal dependent triples are
1824 \[
1825 \{x,p,x+p\},
1826 \quad
1827 \{p,q,p+q\},
1828 \quad
1829 \{x,p+q,x+p+q\},
1830 \quad
1831 \{q,x+p,x+p+q\}.
1832 \]
1833 Under the displayed edge labeling, these are precisely the four triangular cycles of $K_4$.  They determine the rank-three cycle matroid $M(K_4)$, which is regular because it has a totally unimodular representation; see, for example, \cite{g:Oxley2011}.
1834 \end{proof}
1835 
1836 \begin{figure}[t]
1837 \centering
1838 \includegraphics[width=.72\linewidth]{assets/g_regular_matroid_k4.pdf}
1839 \caption{The six carrier states as the edges of $K_4$.  Each triangular cycle is one of the four three-element dependencies in the Pasch configuration.  The resulting regular matroid is representable over every field.}
1840 \label{g:fig:k4-matroid}
1841 \end{figure}
1842 
1843 The field-independent circuit theorem is stronger than matroid representability alone, because it also depends on the ordering and the designated carrier role.  Nevertheless, \cref{g:prop:regular-matroid} explains why the local dependence pattern survives unchanged in every characteristic.
1844 
1845 \subsection{Distance as first arrival}
1846 
1847 Let $G$ be a finite group and $S=S^{-1}$ a symmetric generating set.  On $\ell^2(G)$, let $\lambda$ be the left regular representation,
1848 \[
1849 \lambda(s)\delta_h=\delta_{sh},
1850 \]
1851 and define
1852 \[
1853 A_S=\sum_{s\in S}\lambda(s).
1854 \]
1855 For $g\in G$, define the endpoint Green series
1856 \[
1857 \mathcal G_{S,g}(z)
1858 =
1859 \left\langle
1860 \delta_g,
1861 (I-zA_S)^{-1}\delta_e
1862 \right\rangle.
1863 \]
1864 
1865 \begin{proposition}[First-arrival identity]\label{g:prop:first-arrival}
1866 The coefficient of $z^k$ in $\mathcal G_{S,g}(z)$ is the number of length-$k$ words in $S$ with product $g$.  Hence
1867 \[
1868 d_S(e,g)=\ord_{z=0}\mathcal G_{S,g}(z).
1869 \]
1870 \end{proposition}
1871 
1872 \begin{proof}
1873 Formally,
1874 \[
1875 (I-zA_S)^{-1}=\sum_{k\ge0}z^kA_S^k.
1876 \]
1877 The matrix coefficient $\langle\delta_g,A_S^k\delta_e\rangle$ counts $k$-step walks from $e$ to $g$, which are exactly length-$k$ words with product $g$.  The first nonzero coefficient occurs at the word distance.
1878 \end{proof}
1879 
1880 If
1881 \[
1882 A_S=\sum_\lambda \lambda\Pi_\lambda
1883 \]
1884 is the spectral resolution, then
1885 \[
1886 \mathcal G_{S,g}(z)
1887 =
1888 \sum_\lambda
1889 \frac{\langle\delta_g,\Pi_\lambda\delta_e\rangle}{1-\lambda z}.
1890 \]
1891 Thus eigenvalues alone do not determine first arrival.  The endpoint matrix coefficients of the spectral projectors are essential.
1892 
1893 For the canonical target $C$, exact word counts begin
1894 \begin{align*}
1895 \mathcal G_{\downarrow,C}(z)
1896 &=
1897 543z^7+25080z^8+510703z^9+10824940z^{10}+\cdots,\\
1898 \mathcal G_{*,C}(z)
1899 &=
1900 2z^6+776z^7+39454z^8+\cdots.
1901 \end{align*}
1902 The metric defect is the valuation drop
1903 \[
1904 \ord_0\mathcal G_{\downarrow,C}
1905 -
1906 \ord_0\mathcal G_{*,C}
1907 =1.
1908 \]
1909 
1910 \begin{figure}[t]
1911 \centering
1912 \includegraphics[width=.78\linewidth]{assets/g_green_coefficients.pdf}
1913 \caption{Exact endpoint word counts for the canonical target.  The ambient walk first arrives at length six.  The restricted walk first arrives at length seven.}
1914 \label{g:fig:green-coefficients}
1915 \end{figure}
1916 
1917 Across the twenty defects, the truncated endpoint data split into five Green-signature classes, each of multiplicity four.  The signatures are listed in \cref{g:tab:green-signatures}.
1918 
1919 \begin{table}[t]
1920 \centering
1921 \caption{The five endpoint Green-signature packets.  Each row occurs for four defective targets.}
1922 \label{g:tab:green-signatures}
1923 \resizebox{\textwidth}{!}{%
1924 \begin{tabular}{@{}rrrrrrrr@{}}
1925 \toprule
1926 &\multicolumn{4}{c}{restricted coefficients}&\multicolumn{3}{c}{ambient coefficients}\\
1927 packet&$[z^7]$&$[z^8]$&$[z^9]$&$[z^{10}]$&$[z^6]$&$[z^7]$&$[z^8]$\\
1928 \midrule
1929 1&326&15430&316118&7576819&4&570&23318\\
1930 2&326&15536&321870&7727183&4&570&23318\\
1931 3&543&25080&510703&10824940&2&776&39454\\
1932 4&543&25639&511524&10984988&2&776&39454\\
1933 5&543&26091&511819&11121486&2&776&39454\\
1934 \bottomrule
1935 \end{tabular}}
1936 \end{table}
1937 
1938 \section{Interval-tree certificates and connected higher-dimensional families}\label{g:sec:higher}
1939 
1940 From this point through the rank and tensor arguments, the coefficient domain is a field $\F$.  The six-row atom is the first defect, but it is not an isolated low-dimensional accident.  This section gives a field-independent family of connected targets in every dimension at least seven.  The lower bound is certified by a multiscale rank potential adapted to the ordered flag.
1941 
1942 \subsection{Interval-tree rank potential}
1943 
1944 \begin{definition}[Interval tree]
1945 An \emph{interval tree} on the ordered coordinates $0,1,\ldots,n-1$ is a rooted binary tree whose leaves occur in that order and whose every node is a contiguous interval.  If an internal node $v$ splits its interval into consecutive left and right children $L_v$ and $R_v$, define
1946 \begin{equation}\label{g:eq:tree-potential}
1947 \Phi_T(A)
1948 =
1949 \sum_{v\in\operatorname{Int}(T)}
1950 \rank A[R_v,L_v],
1951 \qquad A\in\U_n(\F).
1952 \end{equation}
1953 \end{definition}
1954 
1955 \begin{lemma}[One-cut locality]\label{g:lem:one-cut-locality}
1956 Let $X\in\U_n(\F)$ and let $X'$ be obtained from $X$ by one lower-directed transvection.  Then
1957 \[
1958 \bigl|\Phi_T(X')-\Phi_T(X)\bigr|\le1.
1959 \]
1960 \end{lemma}
1961 
1962 \begin{proof}
1963 Suppose the gate is $s\to t$ with $s<t$.  Let $v_0$ be the lowest node of $T$ whose two children separate $s$ and $t$.  The order of the leaves forces $s\in L_{v_0}$ and $t\in R_{v_0}$.  At this one node, a single row of the cross block $X[R_{v_0},L_{v_0}]$ changes, so its rank changes by at most one.
1964 
1965 At every ancestor of $v_0$, the two rows lie in the same child.  If that child is the right child, the gate is an internal row operation on the relevant cross block and preserves rank; if it is the left child, the cross block is unchanged.  At a descendant containing $t$ but not $s$, every column of the descendant interval lies strictly to the right of $s$.  Since $X$ remains lower triangular, row $s$ vanishes on those columns, so the descendant block is unchanged.  All other descendants are also unchanged.  Hence only the term at $v_0$ can vary.
1966 \end{proof}
1967 
1968 \begin{corollary}[Interval-tree lower bound]\label{g:cor:tree-lower-bound}
1969 For every $A\in\U_n(\F)$ and every interval tree $T$,
1970 \[
1971 \ellDown(A)\ge\Phi_T(A).
1972 \]
1973 \end{corollary}
1974 
1975 \begin{proof}
1976 The identity has potential zero.  Apply \cref{g:lem:one-cut-locality} along any lower-directed word from the identity to $A$.
1977 \end{proof}
1978 
1979 \begin{definition}[Tree-tight target]\label{g:def:tree-tight}
1980 A lower-unitriangular target $A$ is \emph{tree tight} if some interval tree $T$ satisfies
1981 \[
1982 \Phi_T(A)=\ellDown(A).
1983 \]
1984 \end{definition}
1985 
1986 Tree tightness is stronger than possessing a rank lower bound.  It says that one ordered hierarchy accounts for the entire restricted word length.  The family below is tree tight by construction.
1987 
1988 \subsection{The snapshot family}
1989 
1990 Fix integers
1991 \[
1992 u\ge1,
1993 \qquad
1994 1\le v\le u+1,
1995 \]
1996 and choose distinct phases
1997 \[
1998 0\le s_1<s_2<\cdots<s_v\le u.
1999 \]
2000 Order the coordinates as
2001 \[
2002 x_1,\ldots,x_u,\ p,\ q,\ t_1,\ldots,t_v.
2003 \]
2004 For $0\le s\le u$, put
2005 \begin{equation}\label{g:eq:prefix-state}
2006 w_s=e_p+\sum_{i=1}^{s}e_{x_i}.
2007 \end{equation}
2008 Define
2009 \begin{equation}\label{g:eq:snapshot-target}
2010 A(u;s_1,\ldots,s_v)\in\U_{u+v+2}(\F)
2011 \end{equation}
2012 by
2013 \[
2014 R_{x_i}=e_{x_i},
2015 \qquad
2016 R_p=w_u,
2017 \qquad
2018 R_q=e_q,
2019 \]
2020 and
2021 \begin{equation}\label{g:eq:snapshot-output}
2022 R_{t_j}=e_{t_j}+e_q+w_{s_j}
2023 \qquad(1\le j\le v).
2024 \end{equation}
2025 The output rows record selected intermediate versions of the carrier $p$.
2026 
2027 \begin{proof}[Proof of \cref{g:thm:snapshot-family}]
2028 For the ambient construction, first apply
2029 \[
2030 q\to p.
2031 \]
2032 Sweep through the updates
2033 \[
2034 x_1\to p,\ldots,x_u\to p.
2035 \]
2036 Whenever phase $s_j$ is reached, apply
2037 \[
2038 p\to t_j.
2039 \]
2040 Finally apply $q\to p$ with coefficient $-1$.  At phase $s$, the carrier is $e_q+w_s$, so every output has the required value, and the final gate removes $e_q$ from row $p$.  The word has length
2041 \[
2042 1+u+v+1=u+v+2.
2043 \]
2044 Thus
2045 \[
2046 \ellAll\bigl(A(u;s_1,\ldots,s_v)\bigr)\le u+v+2.
2047 \]
2048 
2049 For a lower word, perform the same $u$ updates without opening the catalyst.  At each selected phase, use the two gates
2050 \[
2051 p\to t_j,
2052 \qquad
2053 q\to t_j.
2054 \]
2055 This gives length $u+2v$.
2056 
2057 It remains to prove optimality in the lower model.  At the root, split
2058 \[
2059 \{x_1,\ldots,x_u,p\}
2060 \quad\big|\quad
2061 \{q,t_1,\ldots,t_v\}.
2062 \]
2063 The nonzero rows of the root cross block are $w_{s_1},\ldots,w_{s_v}$.  Distinct prefix vectors are linearly independent: in a linear relation, inspect successively a coordinate occurring in $w_{s_j}$ but in none of the earlier prefixes, starting from the largest phase.  Hence the root contributes $v$.
2064 
2065 Inside the left child, use the comb that splits off $x_1$, then $x_2$, and so on while retaining $p$ in the remaining interval.  Every one of the $u$ cuts has rank one because the final row $p$ contains every $x_i$.  Inside the right child, repeatedly split off the last output while retaining $q$ in the left interval.  Each of the $v$ cuts has rank one because every output contains $q$.  Therefore
2066 \[
2067 \Phi_T\bigl(A(u;s_1,\ldots,s_v)\bigr)
2068 =v+u+v=u+2v.
2069 \]
2070 The interval-tree lower bound matches the displayed lower circuit.
2071 \end{proof}
2072 
2073 \begin{figure}[t]
2074 \centering
2075 \includegraphics[width=.90\linewidth]{assets/g_snapshot_family.pdf}
2076 \caption{The connected snapshot family.  One temporary upper dependency lets the ambient circuit export $v$ selected prefix states.  A lower-only circuit must insert the $q$ component separately into every output.}
2077 \label{g:fig:snapshot-family}
2078 \end{figure}
2079 
2080 \begin{remark}[Support connectivity]
2081 For $u,v\ge1$, the undirected support graph of $A(u;s_1,\ldots,s_v)-I$ is connected.  Row $p$ joins all update coordinates $x_i$, while every output joins both $p$ and $q$.  The separation below therefore does not arise from a direct sum of independent six-row gadgets.
2082 \end{remark}
2083 
2084 \subsection{Exact higher binary examples}
2085 
2086 The interval tree gives the exact restricted distance in all dimensions.  For the first three higher targets, a separate bidirectional search also proves that the displayed ambient construction is optimal.
2087 
2088 \begin{theorem}[Exact binary cases in dimensions seven through nine]\label{g:thm:higher-exact}
2089 Over $\F_2$, let
2090 \[
2091 H_7=A(2;0,1,2),
2092 \qquad
2093 H_8=A(3;0,1,2),
2094 \qquad
2095 H_9=A(3;0,1,2,3).
2096 \]
2097 Then
2098 \[
2099 (\ellDown(H_7),\ellAll(H_7))=(8,7),
2100 \]
2101 \[
2102 (\ellDown(H_8),\ellAll(H_8))=(9,8),
2103 \]
2104 and
2105 \[
2106 (\ellDown(H_9),\ellAll(H_9))=(11,9).
2107 \]
2108 \end{theorem}
2109 
2110 \begin{proof}
2111 The restricted values follow from \cref{g:thm:snapshot-family}.  The ambient words have lengths $7$, $8$, and $9$.  To exclude shorter words, the supplement computes exact ambient balls and checks that the two relevant balls do not intersect.  The certificate sizes are
2112 \begin{center}
2113 \begin{tabular}{@{}ccll@{}}
2114 \toprule
2115 $n$&tested split&left ball&right ball\\
2116 \midrule
2117 $7$&$3+3$&$23276$&$23276$\\
2118 $8$&$3+4$&$52277$&$1174097$\\
2119 $9$&$4+4$&$2994949$&$2994949$\\
2120 \bottomrule
2121 \end{tabular}
2122 \end{center}
2123 Every intersection is empty.  Since the generating sets are symmetric, an empty radius-$r$ versus radius-$s$ intersection rules out every word of length at most $r+s$.
2124 \end{proof}
2125 
2126 These are exact higher-dimensional examples, not merely padded copies of $C$.
2127 
2128 \subsection{A connected defect in every dimension}
2129 
2130 \begin{proof}[Proof of \cref{g:cor:connected-gap}]
2131 For $n\ge7$, put
2132 \[
2133 v_n=\left\lfloor\frac{n-1}{2}\right\rfloor,
2134 \qquad
2135 u_n=n-v_n-2,
2136 \]
2137 and take the phases
2138 \[
2139 0,1,\ldots,v_n-1.
2140 \]
2141 The inequality $v_n\le u_n+1$ holds, so the snapshot target is defined.  By \cref{g:thm:snapshot-family},
2142 \[
2143 \ellDown(A_n)=u_n+2v_n=n+v_n-2,
2144 \]
2145 while
2146 \[
2147 \ellAll(A_n)\le u_n+v_n+2=n.
2148 \]
2149 Hence
2150 \[
2151 \ellDown(A_n)-\ellAll(A_n)
2152 \ge v_n-2
2153 =
2154 \left\lfloor\frac{n-5}{2}\right\rfloor.
2155 \]
2156 Connectivity follows from the preceding remark.
2157 \end{proof}
2158 
2159 \begin{table}[t]
2160 \centering
2161 \caption{Successive connected cases from the optimized snapshot family.  The restricted value is exact; the ambient column is a certified construction and is exact for $n=7,8,9$ over $\F_2$.}
2162 \label{g:tab:higher-cases}
2163 \begin{tabular}{@{}rrrrr@{}}
2164 \toprule
2165 $n$&$u$&$v$&$\ellDown$&ambient upper bound / certified gap\\
2166 \midrule
2167 $7$&$2$&$3$&$8$&$7\;/\;1$\\
2168 $8$&$3$&$3$&$9$&$8\;/\;1$\\
2169 $9$&$3$&$4$&$11$&$9\;/\;2$\\
2170 $10$&$4$&$4$&$12$&$10\;/\;2$\\
2171 $11$&$4$&$5$&$14$&$11\;/\;3$\\
2172 $12$&$5$&$5$&$15$&$12\;/\;3$\\
2173 $13$&$5$&$6$&$17$&$13\;/\;4$\\
2174 $15$&$6$&$7$&$20$&$15\;/\;5$\\
2175 $17$&$7$&$8$&$23$&$17\;/\;6$\\
2176 $19$&$8$&$9$&$26$&$19\;/\;7$\\
2177 $21$&$9$&$10$&$29$&$21\;/\;8$\\
2178 \bottomrule
2179 \end{tabular}
2180 \end{table}
2181 
2182 \begin{figure}[t]
2183 \centering
2184 \includegraphics[width=.76\linewidth]{assets/g_connected_higher_cases.pdf}
2185 \caption{The six-row atom is the first exact defect.  From dimension seven onward, the connected snapshot family gives an exact restricted length and a shorter ambient construction in every dimension.}
2186 \label{g:fig:higher-cases}
2187 \end{figure}
2188 
2189 The ratio also increases beyond the block-sum value $7/6$.
2190 
2191 \begin{corollary}[Asymptotic multiplicative distortion]\label{g:cor:three-halves}
2192 For every field,
2193 \[
2194 \limsup_{n\to\infty}
2195 \sup_{A\in\U_n(\F),\,A\ne I}
2196 \frac{\ellDown(A)}{\ellAll(A)}
2197 \ge\frac32.
2198 \]
2199 \end{corollary}
2200 
2201 \begin{proof}
2202 Along the optimized connected family,
2203 \[
2204 \frac{\ellDown(A_n)}{\ellAll(A_n)}
2205 \ge
2206 \frac{n+\lfloor(n-1)/2\rfloor-2}{n},
2207 \]
2208 which tends to $3/2$.
2209 \end{proof}
2210 
2211 \section{Bounded and weighted catalytic resources}\label{g:sec:resources}
2212 
2213 The connected snapshot family uses a single matched excursion: one upper-directed gate opens the dirty carrier and one upper-directed gate closes it.  This permits a sharper statement than the unrestricted inequality $\ellAll<\ellDown$.
2214 
2215 \subsection{A bounded number of upper-directed gates}
2216 
2217 For a circuit word $w$, let $u(w)$ denote its number of upper-directed gates.
2218 
2219 \begin{definition}[Upper-gate budget]
2220 For $q\ge0$ and $A\in\U_n(\F)$, define
2221 \[
2222 \ellBudget{q}(A)
2223 =
2224 \min\{|w|:[w]=A,\ u(w)\le q\}.
2225 \]
2226 Thus
2227 \[
2228 \ellBudget{0}(A)=\ellDown(A),
2229 \qquad
2230 \ellBudget{q+1}(A)\le\ellBudget{q}(A),
2231 \qquad
2232 \ellAll(A)\le\ellBudget{q}(A).
2233 \]
2234 \end{definition}
2235 
2236 \begin{proposition}[Two upper gates give a linear advantage]\label{g:prop:two-upper-linear}
2237 For every snapshot target $A=A(u;s_1,\ldots,s_v)$,
2238 \[
2239 \ellBudget{0}(A)=u+2v,
2240 \qquad
2241 \ellBudget{2}(A)\le u+v+2.
2242 \]
2243 Consequently,
2244 \[
2245 \ellBudget{0}(A)-\ellBudget{2}(A)\ge v-2.
2246 \]
2247 For the optimized connected target $A_n$ of \cref{g:cor:connected-gap},
2248 \[
2249 \ellBudget{0}(A_n)-\ellBudget{2}(A_n)
2250 \ge
2251 \left\lfloor\frac{n-5}{2}\right\rfloor.
2252 \]
2253 \end{proposition}
2254 
2255 \begin{proof}
2256 The exact restricted value is \cref{g:thm:snapshot-family}.  Its ambient construction has precisely two upper-directed gates, namely the opening and closing operations on the carrier row; all $u$ updates and all $v$ reads are lower directed.  The optimized choice has $v=\lfloor(n-1)/2\rfloor$.
2257 \end{proof}
2258 
2259 \begin{corollary}[No budget-only additive simulation bound]\label{g:cor:no-budget-only}
2260 There is no finite constant $K$ such that
2261 \[
2262 \ellDown(A)\le\ellBudget{2}(A)+K
2263 \]
2264 for all dimensions, fields, and lower-unitriangular targets $A$.
2265 \end{corollary}
2266 
2267 \begin{proof}
2268 The left-minus-right difference in \cref{g:prop:two-upper-linear} tends to infinity with $n$.
2269 \end{proof}
2270 
2271 Thus the power of the excursion is not controlled by the number of forbidden gates.  It is controlled by how many useful carrier states are exported between opening and closing.
2272 
2273 \subsection{Rank-one, bandwidth-one flag escape}\label{g:subsec:microscopic-escape}
2274 
2275 The number of upper gates does not measure how far a circuit travels from the lower subgroup.  We now control every intermediate state.
2276 
2277 For $X\in\SL_n(\F)$, let $X^+$ be the matrix obtained by retaining only the strict upper entries of $X$.  Define
2278 \[
2279 r^+(X)=\rank X^+
2280 \]
2281 and
2282 \[
2283 b^+(X)=\max\{j-i:X_{ij}\ne0,\ i<j\},
2284 \]
2285 with $b^+(X)=0$ when $X^+=0$.  Let $\ellExc{r}{b}(A)$ be the minimum length of a transvection circuit from $I$ to $A$ such that every prefix matrix $X$ satisfies
2286 \[
2287 r^+(X)\le r,
2288 \qquad
2289 b^+(X)\le b.
2290 \]
2291 
2292 \begin{lemma}\label{g:lem:zero-excursion-equals-lower}
2293 For $A\in\U_n(\F)$,
2294 \[
2295 \ellExc{0}{0}(A)=\ellDown(A).
2296 \]
2297 \end{lemma}
2298 
2299 \begin{proof}
2300 A lower-directed gate preserves lower triangularity.  Conversely, if $X$ is lower unitriangular and an upper-directed gate $R_t\leftarrow R_t+aR_s$ with $t<s$ is applied, then the new $(t,s)$ entry equals
2301 \[
2302 X_{t,s}+aX_{s,s}=a\ne0.
2303 \]
2304 The next state is therefore not lower triangular.  A circuit whose every prefix has zero strict upper part uses only lower-directed gates.
2305 \end{proof}
2306 
2307 \begin{theorem}[Microscopic escape, macroscopic saving]\label{g:thm:microscopic-escape}
2308 For every field $\F$ and every $n\ge7$, there is a connected target $A_n\in\U_n(\F)$ such that
2309 \[
2310 \ellExc{0}{0}(A_n)-\ellExc{1}{1}(A_n)
2311 \ge
2312 \left\lfloor\frac{n-5}{2}\right\rfloor.
2313 \]
2314 The length-$n$ circuit witnessing the second term uses exactly two upper-directed gates.
2315 \end{theorem}
2316 
2317 \begin{proof}
2318 Use the connected family from \cref{g:cor:connected-gap}, with the carrier coordinates $p<q$ adjacent.  Between the opening and closing gates, the only strict upper entry is the coefficient at position $(p,q)$.  Hence every prefix has upper rank at most one and upper bandwidth at most one.  The displayed ambient circuit has length $n$, whereas
2319 \[
2320 \ellExc{0}{0}(A_n)=\ellDown(A_n)
2321 =n+\left\lfloor\frac{n-1}{2}\right\rfloor-2.
2322 \]
2323 Subtracting proves the claim.
2324 \end{proof}
2325 
2326 \begin{figure}[t]
2327 \centering
2328 \includegraphics[width=.82\linewidth]{assets/g_microscopic_escape.pdf}
2329 \caption{The snapshot circuit leaves the lower subgroup through one adjacent upper entry.  Throughout the excursion the strict upper part has rank one and bandwidth one, yet the accumulated saving grows linearly.}
2330 \label{g:fig:microscopic-escape}
2331 \end{figure}
2332 
2333 \subsection{A weighted upper-gate metric}
2334 
2335 A hardware or fault model may penalize an upper-directed interaction more heavily than a lower-directed one.  Fix $\lambda>0$.  If $w$ has $d(w)$ lower-directed gates and $u(w)$ upper-directed gates, put
2336 \[
2337 \operatorname{cost}_{\lambda}(w)=d(w)+\lambda u(w),
2338 \]
2339 and define
2340 \[
2341 \ellWeight{\lambda}(A)
2342 =
2343 \inf\{\operatorname{cost}_{\lambda}(w):[w]=A\}.
2344 \]
2345 At $\lambda=1$ this is the ordinary ambient length, while large $\lambda$ increasingly penalizes flag excursions.
2346 
2347 \begin{proposition}[Fixed penalties do not suppress catalysis]\label{g:prop:weighted-catalysis}
2348 For every snapshot target $A=A(u;s_1,\ldots,s_v)$ and every $\lambda>0$,
2349 \[
2350 \ellWeight{\lambda}(A)
2351 \le
2352 u+v+2\lambda.
2353 \]
2354 Consequently,
2355 \[
2356 \ellDown(A)-\ellWeight{\lambda}(A)
2357 \ge
2358 v-2\lambda.
2359 \]
2360 For the optimized connected family,
2361 \[
2362 \ellDown(A_n)-\ellWeight{\lambda}(A_n)
2363 \ge
2364 \left\lfloor\frac{n-1}{2}\right\rfloor-2\lambda.
2365 \]
2366 In particular, for every fixed finite $\lambda$, the weighted advantage grows linearly with $n$.
2367 \end{proposition}
2368 
2369 \begin{proof}
2370 The displayed catalytic word contains $u+v$ lower-directed gates and two upper-directed gates, so its weighted cost is $u+v+2\lambda$.  Subtract this from the exact restricted value $u+2v$.  The optimized family again has $v=\lfloor(n-1)/2\rfloor$.
2371 \end{proof}
2372 
2373 \begin{remark}[Penalty threshold]
2374 For the displayed realization of a snapshot target, catalysis beats the optimal lower-only cost whenever
2375 \[
2376 \lambda<\frac v2.
2377 \]
2378 The critical penalty therefore scales with the number of consumers, not with the dimension of the dirty workspace.
2379 \end{remark}
2380 
2381 \begin{figure}[t]
2382 \centering
2383 \includegraphics[width=.78\linewidth]{assets/g_weighted_catalysis.pdf}
2384 \caption{Certified lower-minus-weighted advantage for the optimized connected family.  Every fixed upper-gate penalty is eventually amortized because the same matched excursion serves a growing number of output snapshots.}
2385 \label{g:fig:weighted-catalysis}
2386 \end{figure}
2387 
2388 \begin{proof}[Proof of \cref{g:thm:resource-robustness}]
2389 Combine \cref{g:prop:two-upper-linear,g:prop:weighted-catalysis}.
2390 \end{proof}
2391 
2392 
2393 \section{Algebraic rarity of catalytic defects}\label{g:sec:rarity}
2394 
2395 The preceding sections construct highly structured targets with large defects.  This section proves the complementary statement that catalytic defects are nongeneric at every fixed dimension.  Fix a field $K$.  Algebraic dimensions and closures are taken after base change to an algebraic closure of $K$.  Put
2396 \[
2397 N=\dim \U_n=\binom n2,
2398 \qquad
2399 M=n(n-1).
2400 \]
2401 
2402 \subsection{Transvection product loci}
2403 
2404 For a direction skeleton
2405 \[
2406 \sigma=((t_1,s_1),\ldots,(t_L,s_L)),
2407 \qquad t_i\ne s_i,
2408 \]
2409 define the polynomial word map
2410 \[
2411 \Phi_\sigma:\Aff^L\longrightarrow\SL_n,
2412 \qquad
2413 (a_1,\ldots,a_L)
2414 \longmapsto
2415 (I+a_LE_{t_L,s_L})\cdots(I+a_1E_{t_1,s_1}).
2416 \]
2417 The coefficients are allowed to vanish, so a word of length at most $L$ can be padded to length $L$.  Let
2418 \[
2419 \mathcal R^*_{n,\le L}
2420 =
2421 \U_n\cap
2422 \bigcup_{\sigma\in\{(t,s):t\ne s\}^L}
2423 \operatorname{im}\Phi_\sigma
2424 \]
2425 be the ambient reachability locus, and define $\mathcal R^\downarrow_{n,\le L}$ analogously using only lower directions.
2426 
2427 Equivalently, put
2428 \[
2429 X_*
2430 =
2431 \bigcup_{t\ne s}\{I+aE_{t,s}:a\in K\},
2432 \qquad
2433 X_\downarrow
2434 =
2435 \bigcup_{s<t}\{I+aE_{t,s}:a\in K\}.
2436 \]
2437 Then $\ellAll(A)$ and $\ellDown(A)$ are the corresponding transvection product lengths: the least $L$ for which $A\in X_*^L$ or $A\in X_\downarrow^L$.
2438 
2439 \begin{proposition}[Dimension of bounded-length loci]\label{g:prop:reachability-dimension}
2440 For every $L\ge0$, the sets $\mathcal R^*_{n,\le L}$ and $\mathcal R^\downarrow_{n,\le L}$ are constructible and
2441 \[
2442 \dim\overline{\mathcal R^*_{n,\le L}}
2443 \le L,
2444 \qquad
2445 \dim\overline{\mathcal R^\downarrow_{n,\le L}}
2446 \le L.
2447 \]
2448 \end{proposition}
2449 
2450 \begin{proof}
2451 There are finitely many direction skeletons of length $L$.  For each skeleton, $\Phi_\sigma$ is a morphism from an $L$-dimensional affine space.  Chevalley's theorem makes its image constructible, and the closure of the image has dimension at most $L$ \cite{g:Hartshorne1977}.  Finite unions preserve constructibility and the maximum dimension bound.  Intersecting with the closed subvariety $\U_n$ cannot increase dimension.
2452 \end{proof}
2453 
2454 The argument is an instance of a general parameter-counting principle.
2455 
2456 \begin{proposition}[Dimension per gate]\label{g:prop:dimension-per-gate}
2457 Let $G$ be an algebraic group, let $V\subseteq G$ be an irreducible subvariety of dimension $D$, and let $X\subseteq G$ be a finite union of locally closed subvarieties, each of dimension at most $r$, with the identity in $X$.  Write
2458 \[
2459 X^{(L)}
2460 =
2461 \{x_L\cdots x_1:x_1,\ldots,x_L\in X\}.
2462 \]
2463 Then
2464 \[
2465 \dim\overline{V\cap X^{(L)}}\le rL.
2466 \]
2467 In particular, if $rL<D$, a Zariski-generic point of $V$ has $X$-product length greater than $L$.
2468 \end{proposition}
2469 
2470 \begin{proof}
2471 Every irreducible component of the Cartesian power $X^{\times L}$ has dimension at most $rL$.  Multiplication $G^L\to G$ is a morphism, so the closure of the image of each component has dimension at most $rL$.  There are finitely many components, and intersecting the resulting finite union with $V$ cannot increase dimension.  Since the identity belongs to $X$, products of length at most $L$ are already contained in $X^{(L)}$.
2472 \end{proof}
2473 
2474 For transvections, the discrete choice of direction contributes finitely many components and each component carries one scalar parameter.  Thus $r=1$.  Every element of $\U_n(K)$ has lower length at most $N$: process the strict lower entries in any root order compatible with elimination.  The dimension-per-gate bound shows that this worst-case value is generic.
2475 
2476 \begin{theorem}[Generic rigidity]\label{g:thm:generic-rigidity}
2477 Let $K$ be an infinite field.  There is a nonempty Zariski-open subvariety $\Omega_n\subseteq\U_n$, defined over $K$, such that $\Omega_n(K)$ is nonempty and
2478 \[
2479 \ellAll(A)=\ellDown(A)=N
2480 \qquad(A\in\Omega_n(K)).
2481 \]
2482 The same statement holds with exact product length replaced by border product length.
2483 \end{theorem}
2484 
2485 \begin{proof}
2486 After base change to an algebraic closure $\overline K$, \cref{g:prop:reachability-dimension} gives
2487 \[
2488 \dim\overline{\mathcal R^*_{n,\le N-1}}\le N-1<N=\dim\U_n.
2489 \]
2490 Because the word maps are defined over $K$, this proper closed set descends to a proper closed subset of $\U_n$ over $K$.  Its complement is a nonempty Zariski-open set $\Omega_n$.  Since $K$ is infinite and $\U_n\cong\Aff^N$, the set $\Omega_n(K)$ is nonempty and Zariski dense.  For any $A\in\Omega_n(K)$, one has $\ellAll(A)\ge N$.  The inequalities
2491 \[
2492 \ellAll(A)\le\ellDown(A)\le N
2493 \]
2494 force equality.  Replacing each image by its Zariski closure gives the border-length statement by the same argument.
2495 \end{proof}
2496 
2497 \subsection{Defect codimension}
2498 
2499 For an algebraically closed field $K$ and $d\ge1$, define
2500 \[
2501 \mathcal D_{n,\ge d}
2502 =
2503 \{A\in\U_n(K):\DeltaDef(A)\ge d\}.
2504 \]
2505 
2506 \begin{theorem}[Defect--codimension bound]\label{g:thm:defect-codimension}
2507 Let $K$ be algebraically closed.  For every $1\le d\le N$,
2508 \[
2509 \dim\overline{\mathcal D_{n,\ge d}}\le N-d.
2510 \]
2511 Equivalently,
2512 \[
2513 \codim_{\U_n}\overline{\mathcal D_{n,\ge d}}\ge d.
2514 \]
2515 More finely, on the stratum where $\ellDown(A)=L$ and $\DeltaDef(A)\ge d$, the closure has dimension at most $L-d$.
2516 \end{theorem}
2517 
2518 \begin{proof}
2519 If $\DeltaDef(A)\ge d$, then
2520 \[
2521 \ellAll(A)
2522 \le
2523 \ellDown(A)-d
2524 \le
2525 N-d.
2526 \]
2527 Thus $\mathcal D_{n,\ge d}\subseteq\mathcal R^*_{n,\le N-d}$, and \cref{g:prop:reachability-dimension} gives the first assertion.  On the intrinsic-length-$L$ stratum one instead has $\ellAll(A)\le L-d$, proving the refinement.
2528 \end{proof}
2529 
2530 \begin{figure}[t]
2531 \centering
2532 \includegraphics[width=.78\linewidth]{assets/g_defect_strata.pdf}
2533 \caption{Bounded ambient product loci form nested algebraic strata inside $\U_n$.  A defect of size at least $d$ lies inside the ambient reachability locus of length $N-d$, whose closure has codimension at least $d$.}
2534 \label{g:fig:defect-strata}
2535 \end{figure}
2536 
2537 \subsection{Finite-field sparsity}
2538 
2539 The dimension argument has an elementary counting counterpart.  Allowing zero coefficients, a padded word of length $L$ is specified by $L$ choices among $M$ directed positions and $L$ coefficients in $\F_q$.  Consequently
2540 \[
2541 |\mathcal R^*_{n,\le L}(\F_q)|\le(Mq)^L.
2542 \]
2543 
2544 \begin{corollary}[Finite-field defect density]\label{g:cor:finite-field-density}
2545 For $1\le d\le N$,
2546 \[
2547 \Prob_{A\in\U_n(\F_q)}[\DeltaDef(A)\ge d]
2548 \le
2549 \min\{1,M^{N-d}q^{-d}\}.
2550 \]
2551 In particular, for fixed $n$,
2552 \[
2553 \Prob[\DeltaDef(A)>0]=O_n(q^{-1}),
2554 \qquad
2555 \Exp[\DeltaDef(A)]=O_n(q^{-1})
2556 \]
2557 as $q\to\infty$.
2558 \end{corollary}
2559 
2560 \begin{proof}
2561 The defect condition implies ambient length at most $N-d$, so the number of such targets is at most $(Mq)^{N-d}$.  Divide by
2562 \[
2563 |\U_n(\F_q)|=q^N.
2564 \]
2565 The expectation bound follows from
2566 \[
2567 \Exp[\DeltaDef]=\sum_{d=1}^{N}\Prob[\DeltaDef\ge d].
2568 \]
2569 \end{proof}
2570 
2571 The same counting argument also gives
2572 \[
2573 \Prob_{A\in\U_n(\F_q)}[\ellAll(A)=\ellDown(A)=N]
2574 \ge
2575 1-M^{N-1}q^{-1},
2576 \]
2577 whenever the right side is positive.  Thus maximal ambient and intrinsic length is not only Zariski generic over infinite fields but asymptotically typical over growing finite fields at fixed dimension.
2578 
2579 \subsection{Border catalysis}
2580 
2581 For an algebraic generating set $X$, define the border product length
2582 \[
2583 \underline\ell_X(A)
2584 =
2585 \min\{L:A\in\overline{X^L}\}.
2586 \]
2587 This is analogous to the passage from tensor rank to border rank \cite{g:Landsberg2012}.  The generic value is still $N$ by \cref{g:thm:generic-rigidity}, but exact and border defects can differ on exceptional strata.  It is presently open whether the canonical atom $C$ belongs to the closure of the six-factor lower transvection locus.  A negative answer would show that its one-gate defect is stable under algebraic degeneration; a positive answer would exhibit a rank-versus-border-rank phenomenon inside reversible linear synthesis.
2588 
2589 \begin{remark}[Rare but amplifiable]\label{g:rem:rare-amplifiable}
2590 The codimension theorem and the tensor construction point in opposite directions without contradiction.  At each fixed $n$, a defect of size $d$ lies on a codimension-at-least-$d$ subset.  Carefully selected points on these thin strata can nevertheless be tensorized into families with $\Omega(n\log n)$ additive defect.  Catalytic compression is therefore algebraically rare but asymptotically amplifiable.
2591 \end{remark}
2592 
2593 \section{Recursive, block, and tensor amplification}\label{g:sec:amplification}
2594 
2595 \subsection{Restricted block additivity}
2596 
2597 The lower metric is exactly additive on contiguous block-diagonal targets.
2598 
2599 \begin{proposition}[Block additivity]\label{g:prop:block-additivity}
2600 Let $A_i\in\U_{n_i}(\F)$ for $1\le i\le k$.  Then
2601 \[
2602 \ellDown\bigl(\operatorname{diag}(A_1,\ldots,A_k)\bigr)
2603 =
2604 \sum_{i=1}^k\ellDown(A_i).
2605 \]
2606 \end{proposition}
2607 
2608 \begin{proof}
2609 The upper bound follows by running optimal lower circuits independently inside the blocks.
2610 
2611 For the lower bound, view an element of $\U_{n_1+\cdots+n_k}(\F)$ as a lower block-triangular matrix and project to its diagonal blocks:
2612 \[
2613 \pi(X)=(X_{11},\ldots,X_{kk}).
2614 \]
2615 Because diagonal blocks multiply independently in a lower block-triangular product, $\pi$ is a homomorphism.  A lower transvection internal to one block projects to one generator in that factor, while a crossing transvection projects to the identity in every factor.  If $m_i$ gates survive in factor $i$, then the total word length is at least
2616 \[
2617 \sum_i m_i
2618 \ge
2619 \sum_i\ellDown(A_i).
2620 \]
2621 \end{proof}
2622 
2623 The ambient metric is subadditive:
2624 \[
2625 \ellAll\bigl(\operatorname{diag}(A_1,\ldots,A_k)\bigr)
2626 \le
2627 \sum_i\ellAll(A_i).
2628 \]
2629 Cross-block ambient workspace can only improve this upper bound.
2630 
2631 \begin{corollary}[Block-sum amplification]\label{g:cor:linear-gap}
2632 For every field and every $n\ge6$, there is an $A_n\in\U_n(\F)$ with
2633 \[
2634 \ellDown(A_n)-\ellAll(A_n)
2635 \ge
2636 \left\lfloor\frac n6\right\rfloor.
2637 \]
2638 For $n=6k$, the target $C^{\oplus k}$ satisfies
2639 \[
2640 \ellDown(C^{\oplus k})=7k,
2641 \qquad
2642 \ellAll(C^{\oplus k})\le6k.
2643 \]
2644 \end{corollary}
2645 
2646 \begin{proof}
2647 For $n=6k+r$, take $C^{\oplus k}\oplus I_r$ and apply block additivity together with $k$ copies of the ambient six-gate word.
2648 \end{proof}
2649 
2650 \begin{figure}[t]
2651 \centering
2652 \includegraphics[width=.68\linewidth]{assets/g_direct_sum_amplification.pdf}
2653 \caption{Block-sum amplification.  The restricted length is exactly $7k$, while the displayed ambient construction has length $6k$.}
2654 \label{g:fig:direct-sum}
2655 \end{figure}
2656 
2657 \subsection{A recursive zeta-shaped lift}
2658 
2659 For $A\in\U_m(\F)$, define
2660 \begin{equation}\label{g:eq:zeta-lift}
2661 \mathcal Z(A)
2662 =
2663 \begin{pmatrix}
2664 A&0\\
2665 A&A
2666 \end{pmatrix}
2667 \in\U_{2m}(\F).
2668 \end{equation}
2669 
2670 \begin{proposition}[Exact restricted lift]\label{g:prop:zeta-lift}
2671 For every $A\in\U_m(\F)$,
2672 \[
2673 \ellDown(\mathcal Z(A))=2\ellDown(A)+m,
2674 \]
2675 and
2676 \[
2677 \ellAll(\mathcal Z(A))\le2\ellAll(A)+m.
2678 \]
2679 Consequently,
2680 \[
2681 \DeltaDef(\mathcal Z(A))\ge2\DeltaDef(A).
2682 \]
2683 \end{proposition}
2684 
2685 \begin{proof}
2686 The construction first realizes $\operatorname{diag}(A,A)$ and then applies the $m$ root-cross gates that add top row $i$ into bottom row $i$.
2687 
2688 For the lower bound, write a circuit state in $m\times m$ blocks as
2689 \[
2690 X=
2691 \begin{pmatrix}
2692 P&0\\
2693 Q&R
2694 \end{pmatrix}.
2695 \]
2696 Projection to the two diagonal blocks forces at least $2\ellDown(A)$ internal gates.  A top-internal gate leaves $Q$ unchanged.  A bottom-internal gate performs an invertible row operation on $Q$ and preserves its rank.  A root-cross gate changes $Q$ by one rank-one row contribution, so it can increase $\rank Q$ by at most one.  The final cross block is $A$, of rank $m$, hence at least $m$ root-cross gates are necessary.
2697 \end{proof}
2698 
2699 Let $A^{[0]}=A$ and $A^{[r+1]}=\mathcal Z(A^{[r]})$.  If $A$ has size $m$, restricted length $a$, and ambient length $b$, then
2700 \begin{equation}\label{g:eq:zeta-iterate}
2701 \ellDown(A^{[r]})
2702 =
2703 2^r a+r m2^{r-1},
2704 \end{equation}
2705 and
2706 \begin{equation}\label{g:eq:zeta-iterate-ambient}
2707 \ellAll(A^{[r]})
2708 \le
2709 2^r b+r m2^{r-1}.
2710 \end{equation}
2711 Thus
2712 \[
2713 \DeltaDef(A^{[r]})\ge2^r\DeltaDef(A).
2714 \]
2715 For the canonical atom $C$, the first values are
2716 \begin{center}
2717 \begin{tabular}{@{}rrrrr@{}}
2718 \toprule
2719 $r$&dimension&restricted exact&ambient upper bound&certified gap\\
2720 \midrule
2721 $0$&$6$&$7$&$6$&$1$\\
2722 $1$&$12$&$20$&$18$&$2$\\
2723 $2$&$24$&$52$&$48$&$4$\\
2724 $3$&$48$&$128$&$120$&$8$\\
2725 $4$&$96$&$304$&$288$&$16$\\
2726 \bottomrule
2727 \end{tabular}
2728 \end{center}
2729 This gives arbitrarily deep exact recursion with identical diagonal children and a full-rank cross block while preserving a positive defect.
2730 
2731 \begin{figure}[t]
2732 \centering
2733 \includegraphics[width=.88\linewidth]{assets/g_recursive_zeta_lift.pdf}
2734 \caption{The recursive lift has the same outer shape as a Boolean zeta recursion.  A finite defect at the leaf is doubled at every lift.}
2735 \label{g:fig:zeta-lift}
2736 \end{figure}
2737 
2738 \subsection{Tensor products of tree-tight targets}
2739 
2740 The tensor operation gives the stronger asymptotic amplification.
2741 
2742 \begin{theorem}[Exact restricted tensor rule]\label{g:thm:tensor-rule}
2743 Let $A\in\U_m(\F)$ and $B\in\U_n(\F)$ be tree tight.  Then $A\otimes B$ is tree tight and
2744 \begin{equation}\label{g:eq:tensor-lower}
2745 \ellDown(A\otimes B)
2746 =
2747 n\ellDown(A)+m\ellDown(B).
2748 \end{equation}
2749 Moreover,
2750 \begin{equation}\label{g:eq:tensor-ambient}
2751 \ellAll(A\otimes B)
2752 \le
2753 n\ellAll(A)+m\ellAll(B),
2754 \end{equation}
2755 so
2756 \begin{equation}\label{g:eq:tensor-defect}
2757 \DeltaDef(A\otimes B)
2758 \ge
2759 n\DeltaDef(A)+m\DeltaDef(B).
2760 \end{equation}
2761 \end{theorem}
2762 
2763 \begin{proof}
2764 Use lexicographic order on the $mn$ coordinates.  Substitute a copy of a certificate tree for $B$ at every leaf of a certificate tree for $A$.  At an outer node, the cross block is
2765 \[
2766 A[R,L]\otimes B,
2767 \]
2768 whose rank is $n\rank A[R,L]$ because $B$ is invertible.  The outer nodes therefore contribute $n\ellDown(A)$.  The $m$ diagonal copies of the inner tree contribute $m\ellDown(B)$.  This proves the lower bound.
2769 
2770 For the matching lower construction, first realize $I_m\otimes B$ using $m$ copies of a circuit for $B$.  Then realize $A\otimes I_n$.  Each gate of a circuit for $A$ lifts to $n$ coordinatewise gates.  Since
2771 \[
2772 (A\otimes I_n)(I_m\otimes B)=A\otimes B,
2773 \]
2774 the cost is the right side of \cref{g:eq:tensor-lower}.  The same construction with ambient circuits proves \cref{g:eq:tensor-ambient}.
2775 \end{proof}
2776 
2777 If $A$ is tree tight of dimension $m$, with restricted length $a$ and an ambient construction of length $b$, then
2778 \begin{equation}\label{g:eq:tensor-power-lower}
2779 \ellDown(A^{\otimes r})
2780 =
2781 r m^{r-1}a,
2782 \end{equation}
2783 and
2784 \begin{equation}\label{g:eq:tensor-power-upper}
2785 \ellAll(A^{\otimes r})
2786 \le
2787 r m^{r-1}b.
2788 \end{equation}
2789 A positive one-copy defect therefore becomes an order-$N\log N$ defect at dimension $N=m^r$.
2790 
2791 \begin{proof}[Proof of \cref{g:thm:tensor-main}]
2792 Apply \cref{g:thm:tensor-rule} repeatedly to the tree-tight snapshot target $A=A(u;s_1,\ldots,s_v)$, for which
2793 \[
2794 a=u+2v,
2795 \qquad
2796 b=u+v+2=m.
2797 \]
2798 Then
2799 \[
2800 \ellDown(A^{\otimes r})
2801 -
2802 \ellAll(A^{\otimes r})
2803 \ge
2804 r m^{r-1}(v-2).
2805 \]
2806 Since $N=m^r$ and $r=\log_2N/\log_2m$, this is
2807 \[
2808 \frac{v-2}{m\log_2m}N\log_2N.
2809 \]
2810 \end{proof}
2811 
2812 Within the snapshot family, the best coefficient is obtained by the twenty-one-dimensional seed
2813 \[
2814 A_{21}=A(9;0,1,\ldots,9),
2815 \]
2816 for which
2817 \[
2818 \ellDown(A_{21})=29,
2819 \qquad
2820 \ellAll(A_{21})\le21,
2821 \qquad
2822 \DeltaDef(A_{21})\ge8.
2823 \]
2824 
2825 \begin{proposition}[Optimal snapshot seed for tensor rate]\label{g:prop:optimal-snapshot-seed}
2826 Among all snapshot targets, the coefficient
2827 \[
2828 \frac{v-2}{m\log_2m},
2829 \qquad m=u+v+2,
2830 \]
2831 is maximized at
2832 \[
2833 (m,u,v)=(21,9,10).
2834 \]
2835 \end{proposition}
2836 
2837 \begin{proof}
2838 For fixed $m$, maximize $v$ subject to $v\le u+1$ and $u+v+2=m$.  Thus
2839 \[
2840 v=\left\lfloor\frac{m-1}{2}\right\rfloor.
2841 \]
2842 If $m$ is even and at least eight, its coefficient is strictly smaller than that of $m-1$, because the numerator is the same while
2843 \[
2844 (m-1)\log(m-1)<m\log m.
2845 \]
2846 It therefore suffices to consider odd $m$.  Apart from the constant change of logarithm base, the odd-dimensional envelope is
2847 \[
2848 f(x)=\frac{x-5}{2x\log x}.
2849 \]
2850 Its derivative has the sign of
2851 \[
2852 5(1+\log x)-x.
2853 \]
2854 For $x>5$ this expression crosses zero exactly once, between $19$ and $21$.  Direct comparison gives $f(21)>f(19)$, after which the envelope decreases.  Hence the unique integer maximizer is $m=21$.
2855 \end{proof}
2856 
2857 The first tensor powers are
2858 \begin{center}
2859 \begin{tabular}{@{}rrrrr@{}}
2860 \toprule
2861 $r$&dimension $21^r$&restricted exact&ambient upper bound&certified gap\\
2862 \midrule
2863 $1$&$21$&$29$&$21$&$8$\\
2864 $2$&$441$&$1218$&$882$&$336$\\
2865 $3$&$9261$&$38367$&$27783$&$10584$\\
2866 $4$&$194481$&$1074276$&$777924$&$296352$\\
2867 \bottomrule
2868 \end{tabular}
2869 \end{center}
2870 
2871 \begin{figure}[t]
2872 \centering
2873 \includegraphics[width=.74\linewidth]{assets/g_tensor_amplification.pdf}
2874 \caption{Tensor powers of the twenty-one-dimensional snapshot seed.  Both displayed circuit sizes are of order $N\log N$, and their difference has a positive $N\log N$ coefficient.}
2875 \label{g:fig:tensor-amplification}
2876 \end{figure}
2877 
2878 \subsection{Stable tensor capacity and activation}\label{g:subsec:stable-tensor}
2879 
2880 The tensor inequality also defines a regularized ambient invariant.  Let $A\in\U_m(\F)$ and put
2881 \[
2882 b_r(A)
2883 =
2884 \frac{\ellAll(A^{\otimes r})}{m^{r-1}}.
2885 \]
2886 Applying \cref{g:eq:tensor-ambient} to $A^{\otimes r}\otimes A^{\otimes s}$ gives
2887 \[
2888 b_{r+s}(A)\le b_r(A)+b_s(A).
2889 \]
2890 
2891 \begin{proposition}[Stable tensor length]\label{g:prop:stable-tensor-length}
2892 The limit
2893 \[
2894 \tau_*(A)
2895 =
2896 \lim_{r\to\infty}
2897 \frac{\ellAll(A^{\otimes r})}{r m^{r-1}}
2898 =
2899 \inf_{r\ge1}
2900 \frac{\ellAll(A^{\otimes r})}{r m^{r-1}}
2901 \]
2902 exists.  If $A$ is tree tight, then the stable catalytic capacity
2903 \[
2904 \kappa_\otimes(A)
2905 =
2906 \ellDown(A)-\tau_*(A)
2907 \]
2908 satisfies
2909 \[
2910 \kappa_\otimes(A)\ge\DeltaDef(A).
2911 \]
2912 \end{proposition}
2913 
2914 \begin{proof}
2915 The sequence $b_r(A)$ is subadditive, so Fekete's lemma gives the displayed limit.  Since the one-copy lifted construction implies $\tau_*(A)\le\ellAll(A)$, one has
2916 \[
2917 \kappa_\otimes(A)
2918 \ge
2919 \ellDown(A)-\ellAll(A)
2920 =
2921 \DeltaDef(A).
2922 \]
2923 For a tree-tight target, \cref{g:eq:tensor-power-lower} identifies $\ellDown(A)$ with its exact normalized restricted tensor cost.
2924 \end{proof}
2925 
2926 For the twenty-one-dimensional seed $A_{21}$,
2927 \[
2928 \kappa_\otimes(A_{21})\ge8.
2929 \]
2930 This regularization introduces a new possibility: a target may have $\DeltaDef(A)=0$ but $\kappa_\otimes(A)>0$.  In that case one copy is rigid while many tensor copies admit a collective shortcut.  We call this \emph{tensor activation}.
2931 
2932 \subsection{Extremal consequences}
2933 
2934 Define
2935 \[
2936 D_n(\F)
2937 =
2938 \sup_{A\in\U_n(\F)}
2939 \bigl(\ellDown(A)-\ellAll(A)\bigr).
2940 \]
2941 For finite fields the supremum is a maximum.  The tensor family gives the following explicit all-dimension bound.
2942 
2943 \begin{proof}[Proof of \cref{g:cor:nlogn-gap}]
2944 Let $m=21$ and write
2945 \[
2946 n=\sum_{j=0}^{r}d_jm^j,
2947 \qquad
2948 0\le d_j<m.
2949 \]
2950 Take the block sum of $d_j$ copies of $A_{21}^{\otimes j}$ for every $j$, with the convention $A_{21}^{\otimes0}=I_1$.  Block additivity and the tensor estimate give
2951 \[
2952 D_n(\F)
2953 \ge
2954 \frac{8}{21}
2955 \sum_{j=0}^{r}j d_j21^j.
2956 \]
2957 Put $S=\sum_j j d_j21^j$.  Since $r=\lfloor\log_{21}n\rfloor$,
2958 \[
2959 r n-S
2960 =
2961 \sum_{j<r}(r-j)d_j21^j
2962 \le
2963 20\sum_{h\ge1}h21^{r-h}
2964 \le
2965 \frac{21^{r+1}}{20}
2966 \le
2967 \frac{21}{20}n.
2968 \]
2969 Also $r\ge\log_{21}n-1$.  Therefore
2970 \[
2971 S\ge n\log_{21}n-\frac{41}{20}n.
2972 \]
2973 Multiplying by $8/21$ yields
2974 \[
2975 D_n(\F)
2976 \ge
2977 \frac{8}{21\log_2 21}n\log_2n
2978 -
2979 \frac{82}{105}n.
2980 \]
2981 \end{proof}
2982 
2983 Numerically,
2984 \[
2985 \frac{8}{21\log_2 21}
2986 =0.0867315\ldots.
2987 \]
2988 The elementary bottom-to-top construction gives
2989 \[
2990 D_n(\F)\le\frac{n(n-1)}2.
2991 \]
2992 Thus the current general range is
2993 \begin{equation}\label{g:eq:defect-range}
2994 0.0867315\,n\log_2n-O(n)
2995 \le
2996 D_n(\F)
2997 \le
2998 \frac{n(n-1)}2.
2999 \end{equation}
3000 
3001 \section{Discussion and open problems}\label{g:sec:discussion}
3002 
3003 \subsection{What the threshold and higher families establish}
3004 
3005 The six-row atom proves that an optimal circuit for a lower-unitriangular target need not remain in the lower-unitriangular subgroup.  The exact binary classification shows that this first failure is rigid: it occurs for exactly twenty targets, every defect is $(7,6)$, and every target is generated by the same three-cross, one-phase mechanism.
3006 
3007 The higher-dimensional results change the scale of the phenomenon.  The connected snapshot family shows that exactly two upper-directed gates can support a defect linear in dimension, and that the advantage persists under every fixed finite penalty on those gates.  The recursive lift shows that a defective leaf survives arbitrarily many identical full-rank dyadic levels.  Tensor products then turn any tree-tight positive-defect atom into an order-$N\log N$ additive separation.  Thus the defect is not a finite anomaly and not merely linear in the worst case.  At the same time, generic rigidity and the defect--codimension theorem show that large defects require correspondingly special algebraic conditions.  The central synthesis is therefore not ubiquity but amplification: thin exceptional strata can control large structured families.
3008 
3009 \subsection{Relation to ordinary CNOT synthesis}
3010 
3011 Exact CNOT synthesis usually minimizes $\ellAll$ on all of $\GL_n(\F_2)$.  The present problem fixes a structured target class and compares the ambient optimum with a structure-preserving optimum.  Recent exact methods explore the full Cayley graph using symmetries, bidirectional search, A* methods, SAT, and related techniques \cite{g:ChristensenEtAl2025,g:WebsterEtAl2025,g:ShaikVanDePol2025}.  The right-coset computation in this paper is tailored to a subgroup comparison, while the higher-dimensional exact audits use direct bidirectional balls for selected targets.
3012 
3013 The 2026 NP-completeness result for all-to-all CNOT distance shows that cancellation and unrestricted parity reuse must be handled in full generality \cite{g:AcuavivaEtAl2026}.  The present constructions isolate explicit reusable-carrier mechanisms under an ordered restriction.  They do not resolve ambient synthesis complexity.
3014 
3015 \subsection{Open directions}
3016 
3017 \begin{question}[Universal six-dimensional threshold]
3018 Is six the first defective dimension over every field, or even over every nonzero commutative ring?  The atom gives a universal defective target in dimension six.  Exact no-defect searches below six are proved here for $\F_2$ and $\F_3$.
3019 \end{question}
3020 
3021 \begin{question}[Geometry of the defect locus]
3022 For fixed $n$ and $d$, determine the irreducible components and exact dimension of $\overline{\mathcal D_{n,\ge d}}$.  When is the lower bound $\codim\ge d$ sharp?
3023 \end{question}
3024 
3025 \begin{question}[Border catalysis]
3026 Does the canonical atom have lower border product length six or seven?  More generally, when can exact catalytic defects disappear under algebraic degeneration?
3027 \end{question}
3028 
3029 \begin{question}[Correct growth of the maximum defect]
3030 Is $D_n(\F)$ of order $n\log n$, or can interacting catalysts produce a larger power of $n$?  The current bounds are
3031 \[
3032 \Omega(n\log n)
3033 \le
3034 D_n(\F)
3035 \le
3036 O(n^2).
3037 \]
3038 \end{question}
3039 
3040 \begin{question}[Multiplicative distortion]
3041 Is
3042 \[
3043 \sup_{n,A\in\U_n(\F)}
3044 \frac{\ellDown(A)}{\ellAll(A)}
3045 \]
3046 bounded?  The connected snapshot family gives an asymptotic lower bound of $3/2$.  Exceeding $3/2$ appears to require a mechanism beyond one clean carrier exporting independent snapshots.
3047 \end{question}
3048 
3049 \begin{question}[Exact ambient complexity of snapshot targets]
3050 For which phase sets is the ambient construction of length $u+v+2$ optimal?  It is exact for the displayed binary targets in dimensions seven, eight, and nine, but the general ambient optimum remains open.
3051 \end{question}
3052 
3053 \begin{question}[Tensor synergy and activation]
3054 Can $A\otimes B$ admit an ambient circuit shorter than the lifted bound
3055 \[
3056 n\ellAll(A)+m\ellAll(B)?
3057 \]
3058 Such synergy would only increase the defect, but understanding it is necessary for exact tensor complexity.  Does there exist a tree-tight target with $\DeltaDef(A)=0$ but $\kappa_\otimes(A)>0$?
3059 \end{question}
3060 
3061 \begin{question}[Higher catalytic normal forms]
3062 Can interacting or crossing catalytic excursions produce asymptotic behavior impossible for a single clean carrier?  A useful classification would separate laminar, crossing, and singular flag excursions.
3063 \end{question}
3064 
3065 \begin{question}[Two-gate multiplicative ceiling]
3066 Among targets realizable with at most two upper-directed gates, is the asymptotic multiplicative distortion at most $3/2$?  The snapshot family reaches this value from below, but the present paper proves no matching upper bound.
3067 \end{question}
3068 
3069 \begin{question}[Matroidal classification]
3070 Which regular matroids admit a flagged realization whose shortest ambient state tour is strictly shorter than every flag-compatible lift?  The first atom is the graphic matroid $M(K_4)$ with designated source, carrier, and output roles.
3071 \end{question}
3072 
3073 \begin{question}[Weighted phase transition]
3074 For a fixed target family, determine the exact critical penalty $\lambda_c$ at which a flag excursion ceases to improve the optimal weighted cost.  The snapshot construction proves only the lower bound $\lambda_c\ge v/2$ for its displayed carrier word.
3075 \end{question}
3076 
3077 \begin{question}[Other root systems]
3078 Let $G$ be a split reductive group with unipotent radical $U$.  Compare word length in positive root subgroups with ambient word length using all root subgroups.  Which root systems admit a catalytic defect, and what is the first rank?
3079 \end{question}
3080 
3081 \begin{question}[Certificate extraction]
3082 Can exact ambient lower bounds for large structured targets be accompanied by short human-readable certificates rather than exhaustive balls?  The interval-tree method completely handles the restricted side, while the ambient side still lacks an equally general certificate.
3083 \end{question}
3084 
3085 
3086 \section{The twenty binary dimension-six defects}\label{g:app:twenty}
3087 
3088 A lower-unitriangular binary matrix is encoded by reading the strict lower entries row by row:
3089 \[
3090 (1,0),
3091 (2,0),(2,1),
3092 \ldots,
3093 (5,0),\ldots,(5,4).
3094 \]
3095 The resulting fifteen-bit integer is denoted by $\operatorname{code}(A)$.  A row is displayed as the integer whose binary expansion is its support vector.  \Cref{g:tab:twenty} lists all defects.  Every row has $\ellDown=7$ and $\ellAll=6$.
3096 
3097 \begin{longtable}{@{}rllllll@{}}
3098 \caption{The twenty defective matrices in $\U_6(\F_2)$.}\label{g:tab:twenty}\\
3099 \toprule
3100 code&$R_0$&$R_1$&$R_2$&$R_3$&$R_4$&$R_5$\\
3101 \midrule
3102 \endfirsthead
3103 \toprule
3104 code&$R_0$&$R_1$&$R_2$&$R_3$&$R_4$&$R_5$\\
3105 \midrule
3106 \endhead
3107 6585&1&3&4&15&22&38\\
3108 6641&1&3&4&14&23&38\\
3109 6649&1&3&4&15&23&38\\
3110 7601&1&3&4&14&22&39\\
3111 7609&1&3&4&15&22&39\\
3112 7665&1&3&4&14&23&39\\
3113 10014&1&2&7&11&28&41\\
3114 11038&1&2&7&11&28&42\\
3115 12894&1&2&7&11&25&44\\
3116 12958&1&2&7&11&26&44\\
3117 13142&1&2&7&10&29&44\\
3118 13198&1&2&7&9&30&44\\
3119 14102&1&2&7&10&28&45\\
3120 15118&1&2&7&9&28&46\\
3121 17912&1&2&4&15&23&49\\
3122 18936&1&2&4&15&23&50\\
3123 19960&1&2&4&15&23&51\\
3124 20984&1&2&4&15&23&52\\
3125 22008&1&2&4&15&23&53\\
3126 23032&1&2&4&15&23&54\\
3127 \bottomrule
3128 \end{longtable}
3129 
3130 For example, the canonical target has row encoding
3131 \[
3132 (1,3,4,14,23,39)
3133 \]
3134 and code $7601$.
3135 
3136 \section{Search algorithms and correctness}\label{g:app:algorithms}
3137 
3138 \subsection{Restricted search}
3139 
3140 For $\F_2$, each lower-unitriangular matrix is stored as a bit string.  Standard breadth-first search gives exact distance because every edge has unit weight.  The algorithm terminates after visiting all states.
3141 
3142 \begin{algorithm}[Restricted breadth-first search]
3143 Initialize $d[I]=0$ and a queue containing $I$.  Repeatedly remove $X$ from the queue.  For every lower transvection $s\to t$, form $Y=\tau_{t,s}(1)X$.  If $Y$ has not been visited, set $d[Y]=d[X]+1$ and append $Y$.  Continue until the queue is empty.
3144 \end{algorithm}
3145 
3146 \subsection{Right-coset key}
3147 
3148 For an invertible binary matrix $A$, let $c_j$ be column $j$.  Starting at $j=n-1$ and moving left, reduce $c_j$ by the already canonicalized columns $c_{j+1},\ldots,c_{n-1}$, using their pivot coordinates.  The resulting ordered reduced columns form the key $\kappa(A)$.
3149 
3150 \begin{lemma}
3151 For $A,B\in\GL_n(\F_2)$,
3152 \[
3153 \kappa(A)=\kappa(B)
3154 \quad\Longleftrightarrow\quad
3155 AU_n=BU_n.
3156 \]
3157 \end{lemma}
3158 
3159 \begin{proof}
3160 Right multiplication by $U\in\U_n$ replaces column $j$ by itself plus a combination of columns with index greater than $j$.  Right-to-left reduction is therefore unchanged on a right coset.  Conversely, equal reduced columns imply that the original column frames differ by a unique lower-unitriangular column transformation, so $A=BU$ for some $U\in\U_n$.
3161 \end{proof}
3162 
3163 \subsection{Ambient search}
3164 
3165 \begin{algorithm}[Radius-four right-coset meet in the middle]
3166 Compute the exact radius-four ball $B_4$ in $\GL_6(\F_2)$.  Bucket its elements by $\kappa$.  For each bucket and every ordered pair $(b,a)$ in that bucket, compute $u=b^{-1}a\in\U_6$ and update
3167 \[
3168 d_*(u)\leftarrow
3169 \min\bigl(d_*(u),d(b)+d(a)\bigr).
3170 \]
3171 \end{algorithm}
3172 
3173 Correctness is \cref{g:lem:mitm-complete}.  The computation also checks that every generated pair lies in $\U_6$ and that every one of the $32768$ targets receives a finite distance.
3174 
3175 \subsection{Higher-dimensional bidirectional audits}
3176 
3177 For the targets $H_7,H_8,H_9$ of \cref{g:thm:higher-exact}, the program \texttt{small\_snapshot\_exact.cpp} constructs exact ambient balls from the identity and from the target.  If radius-$r$ and radius-$s$ balls are disjoint, symmetry of the generating set rules out every word of length at most $r+s$.  The tested splits are $3+3$, $3+4$, and $4+4$, respectively.  The source stores matrices in one 128-bit word and uses exact row-addition transitions; no probabilistic or floating-point step occurs.
3178 
3179 \subsection{Symbolic higher-family checks}
3180 
3181 The program \texttt{higher\_family\_tests.py} generates the snapshot targets over $\F_2$, $\F_3$, and $\F_5$, evaluates both displayed circuits, computes the interval-tree potentials, audits a tensor certificate for the seven-dimensional seed, verifies the recursive cross rank, and reproduces the twenty-one-dimensional rate optimization.
3182 
3183 \subsection{Further generalization audits}
3184 
3185 The program \texttt{further\_generalization\_tests.py} verifies the universal circuits over $\mathbb Z/4\mathbb Z$, $\mathbb Z/6\mathbb Z$, and $\mathbb Z/8\mathbb Z$, audits the rank-one bandwidth-one excursion, checks the finite-field counting bounds symbolically, and verifies the stable tensor subadditivity identities.
3186 
3187 \subsection{Motif comparison}
3188 
3189 The motif program independently loops over the three adjacent catalyst positions, the phase orientation, the phase leaf, and every nonempty proper before/after subset.  It evaluates each six-gate word from the identity and stores its target.  The resulting set has size twenty.  Exact comparison with the twenty census defects returns equality.
3190 
3191 \section{Reproducibility ledger}\label{g:app:reproducibility}
3192 
3193 The ancillary directory \texttt{supplement/} contains portable source, frozen expected outputs, and a one-command driver:
3194 \begin{verbatim}
3195 cd supplement
3196 ./run_all.sh
3197 \end{verbatim}
3198 The driver compiles every C++ search, executes the Python motif, higher-family, matroid, and weighted-resource checks, and compares all generated outputs byte for byte with the frozen records.  The supplement README gives the individual commands and the role of every program.  A SHA-256 manifest covers every included source and expected-output file.
3199 
3200 \section*{Acknowledgement of computational status}
3201 
3202 All theorem statements are labeled by proof type in the body.  The universal ring-valued atom, Schreier-holonomy interpretation, regular-matroid identification, interval-tree family, bounded, weighted, and microscopic resource theorems, algebraic-rarity bounds, block additivity, recursive lift, tensor rule, stable tensor limit, and asymptotic amplification are proved symbolically.  The first-threshold classification, finite censuses, and exact ambient values in dimensions seven through nine are computer assisted, with complete search-space coverage justified in \cref{g:app:algorithms}.
3203 
3204 \section*{Data and code availability}
3205 
3206 The source archive accompanying this paper contains the complete LaTeX source, all vector figures, every C++ and Python verification program, frozen expected outputs, and SHA-256 manifests.  The command
3207 \begin{verbatim}
3208 cd supplement
3209 ./run_all.sh
3210 \end{verbatim}
3211 rebuilds the finite searches and symbolic audits and compares every output byte for byte with its frozen record.  No randomized or floating-point decision enters a theorem certificate.
3212 
3213 
3214 \chapter{Quantum and reversible gate families}
3215 \section{Qudit SUM gates and ring-valued linear logic}\label{g:ch:qudit-sum}
3216 \index{qudit SUM gate}
3217 \index{controlled addition}
3218 \index{ring universality}
3219 
3220 
3221 \subsection{From transvections to quantum gates}
3222 Let $d\ge2$.  On $n$ qudits with computational basis labeled by $\Z_d^n$, define the scaled SUM gate
3223 \[
3224 \SUM^{(a)}_{s\to t}
3225 \ket{x_0,\ldots,x_{n-1}}
3226 =
3227 \ket{x_0,\ldots,x_t+a x_s,\ldots,x_{n-1}},
3228 \qquad a\in\Z_d.
3229 \]
3230 It is a permutation unitary.  Its action on basis labels is the row transvection
3231 \[
3232 I+aE_{t,s}.
3233 \]
3234 For $d=2$ and $a=1$, it is CNOT.  For prime $d$, these gates lie in the standard qudit Clifford group.  For composite $d$, they remain exact reversible modular-addition gates.
3235 
3236 \begin{provedbox}
3237 The universal six-row atom in the core chapter is valid over every nonzero commutative ring with identity.  Taking $R=\Z_d$ gives a six-qudit target with restricted directed-SUM length seven and ambient all-direction SUM length six for every $d\ge2$.
3238 \end{provedbox}
3239 
3240 \subsection{The universal six-qudit circuit}
3241 Use the coordinate names
3242 \[
3243 x,p,q,t_0,t_1,t_2.
3244 \]
3245 The target acts on basis labels by
3246 \begin{align*}
3247 p&\mapsto p+x,\\
3248 t_0&\mapsto t_0+p+q,\\
3249 t_1&\mapsto t_1+x+p+q,\\
3250 t_2&\mapsto t_2+x+p+q,
3251 \end{align*}
3252 with $x$ and $q$ unchanged.  An ambient word is
3253 \[
3254 \SUM_{q\to p},
3255 \quad
3256 \SUM_{p\to t_0},
3257 \quad
3258 \SUM_{x\to p},
3259 \quad
3260 \SUM_{p\to t_1},
3261 \quad
3262 \SUM_{p\to t_2},
3263 \quad
3264 \SUM^{(-1)}_{q\to p}.
3265 \]
3266 The first gate adds the dirty $q$ component to $p$.  The middle gates export two different carrier states.  The final inverse gate restores $p$.
3267 
3268 \begin{figure}[ht]
3269 \centering
3270 \includegraphics[width=.96\textwidth]{assets/g_qudit_sum_circuit.pdf}
3271 \caption{The universal six-qudit catalytic circuit.  Coefficients are interpreted modulo $d$.}
3272 \label{g:fig:qudit-sum}
3273 \end{figure}
3274 
3275 A lower-only word needs seven gates.  The exact proof is coefficient-domain independent because it uses pivot support and the number of distinct carrier states rather than division.
3276 
3277 \subsection{Connected higher-dimensional qudit families}
3278 The snapshot target $A(u;s_1,\ldots,s_v)$ from the core chapter is defined over any coefficient ring for which the displayed additions make sense.  Over $\Z_d$, it becomes a modular SUM circuit.  Its explicit ambient word uses exactly two reverse-directed SUM gates and has length
3279 \[
3280 u+v+2.
3281 \]
3282 The interval-tree proof of exact restricted length is most transparent over fields, but the displayed upper-bound and resource-amortization mechanism remain valid over every $\Z_d$.
3283 
3284 For a field $\F_q$, the exact formula is
3285 \[
3286 \ellDown(A)=u+2v,
3287 \qquad
3288 \ellAll(A)\le u+v+2,
3289 \]
3290 so
3291 \[
3292 \Delta(A)\ge v-2.
3293 \]
3294 The connected family has asymptotic ratio approaching $3/2$.
3295 
3296 \subsection{Weighted physical costs}
3297 Suppose forward SUM gates cost one and reverse-directed SUM gates cost $\lambda$.  The displayed word has weighted cost
3298 \[
3299 u+v+2\lambda,
3300 \]
3301 while the restricted construction costs $u+2v$.  Hence the gain is at least
3302 \[
3303 v-2\lambda.
3304 \]
3305 This formula can be combined with hardware calibration.  If reverse orientation requires echo pulses or routing, the catalyst remains useful when the number of exported snapshots exceeds twice the effective penalty.
3306 
3307 \begin{boundarybox}
3308 A gate-count saving does not imply a lower physical error or depth.  Device-specific conclusions require a cost vector containing duration, infidelity, crosstalk, and routing.  The algebraic theorem identifies candidate rewrites and the exact break-even inequality.
3309 \end{boundarybox}
3310 
3311 \subsection{Pauli action for prime qudits}
3312 For odd prime $d$, let $X$ and $Z$ denote generalized Pauli operators.  The SUM gate acts by
3313 \begin{align*}
3314 X_s&\mapsto X_sX_t^a,
3315 &
3316 X_t&\mapsto X_t,\\
3317 Z_s&\mapsto Z_s,
3318 &
3319 Z_t&\mapsto Z_s^{-a}Z_t.
3320 \end{align*}
3321 Thus the modular linear action embeds into a symplectic transformation.  The catalytic row excursion has a dual Pauli interpretation: a temporary reverse dependency changes both $X$ propagation and the contragredient $Z$ propagation, then restores them.
3322 
3323 This makes the SUM family a bridge between the transvection paper and the Clifford chapter.  It is the only quantum extension in this monograph that follows directly from the ring-universal theorem without a new finite search.
3324 
3325 \subsection{Continuous-variable shear analogue}
3326 On continuous variables, a linear coordinate map $A$ embeds symplectically as
3327 \[
3328 A\longmapsto
3329 \begin{pmatrix}
3330 A&0\\
3331 0&A^{-T}
3332 \end{pmatrix}.
3333 \]
3334 A row shear therefore gives a Gaussian SUM transformation.  The six-row word identity remains a matrix identity in the corresponding shear subgroup.
3335 
3336 \begin{skeletonbox}
3337 To claim an advantage in a full Gaussian gate library, one must compare against rotations, squeezers, beam splitters, and general symplectic decompositions.  The current theorem proves a defect only inside the directed-shear versus all-shear comparison.
3338 \end{skeletonbox}
3339 
3340 \subsection{Compiler primitive}
3341 A compiler can search for a carrier row $p$, a temporary source $q$, and output rows requiring several successive states of $p$.  The symbolic pattern is:
3342 \begin{enumerate}
3343 \item add $q$ into $p$ in the disallowed direction,
3344 \item update $p$ through a sequence of allowed additions,
3345 \item copy selected intermediate states of $p$ into outputs,
3346 \item subtract $q$ from $p$,
3347 \item verify that the outputs contain the intended modular combinations.
3348 \end{enumerate}
3349 The Python function \texttt{snapshot\_target} constructs the target and \texttt{snapshot\_ambient\_word} emits the word.
3350 
3351 \begin{lstlisting}[style=pythonstyle,caption={Constructing a modular snapshot family.}]
3352 from catalytic_gate_atlas.linear import (
3353     snapshot_target,
3354     snapshot_ambient_word,
3355     apply_row_word,
3356 )
3357 
3358 u = 4
3359 phases = [0, 2, 4]
3360 modulus = 5
3361 A = snapshot_target(u, phases, modulus)
3362 word = snapshot_ambient_word(u, phases, modulus)
3363 assert apply_row_word(len(A), word, modulus) == A
3364 \end{lstlisting}
3365 
3366 \subsection{Open qudit questions}
3367 \begin{question}
3368 Does the first defective dimension remain six for every finite field and every modular ring $\Z_d$ under the directed-SUM metric?
3369 \end{question}
3370 \begin{question}
3371 Can qudit Clifford gates outside the SUM subgroup produce a larger defect for a SUM target under total, entangling, or depth cost?
3372 \end{question}
3373 \begin{question}
3374 Do composite dimensions admit characteristic-dependent catalytic motifs unavailable over fields?
3375 \end{question}
3376 
3377 \section{Catalytic basis escape in symplectic Clifford synthesis}\label{g:ch:clifford}
3378 \index{Clifford group}
3379 \index{symplectic group}
3380 \index{parabolic subgroup}
3381 \index{CSS circuit}
3382 \index{entangling count}
3383 
3384 
3385 \subsection{Binary symplectic representation}
3386 Modulo global phase and Pauli translations, an $n$-qubit Clifford operation acts on Pauli exponent vectors
3387 \[
3388 v=(x_0,\ldots,x_{n-1}\mid z_0,\ldots,z_{n-1})^T\in\F_2^{2n}
3389 \]
3390 through a symplectic matrix
3391 \[
3392 M\in\Sp(2n,2).
3393 \]
3394 The elementary gates used here act as follows:
3395 \begin{align*}
3396 H_i &: (x_i,z_i)\mapsto(z_i,x_i),\\
3397 S_i &: z_i\mapsto z_i+x_i,\\
3398 \CX_{i\to j} &: x_j\mapsto x_j+x_i,
3399 \quad z_i\mapsto z_i+z_j,\\
3400 \CZ_{ij} &: z_i\mapsto z_i+x_j,
3401 \quad z_j\mapsto z_j+x_i.
3402 \end{align*}
3403 
3404 Let $P_n\le\Sp(2n,2)$ be the parabolic subgroup stabilizing the $Z$ Lagrangian
3405 \[
3406 L_Z=\{(0\mid z):z\in\F_2^n\}.
3407 \]
3408 The gates $S$, $\CZ$, and $\CX$ preserve $L_Z$.  Hadamard gates do not.
3409 
3410 \begin{definition}[Parabolic and ambient Clifford metrics]
3411 The restricted alphabet is
3412 \[
3413 \mathcal S_P
3414 =
3415 \{S_i,\CZ_{ij},\CX_{i\to j}\},
3416 \]
3417 and the ambient alphabet is
3418 \[
3419 \mathcal S_C
3420 =
3421 \mathcal S_P\cup\{H_i\}.
3422 \]
3423 Targets lie in $P_n$.  We study both total primitive count and entangling count, where $H_i$ and $S_i$ have cost zero while $\CX$ and $\CZ$ have cost one.
3424 \end{definition}
3425 
3426 This is a precise basis-escape model.  It is not the unique meaning of ``CSS preserving'' or ``Clifford cost.''  It is chosen because both groups are finite and the restricted subgroup has a clean Lagrangian interpretation.
3427 
3428 \subsection{Exact group sizes}
3429 The finite state spaces are
3430 \[
3431 |P_n|
3432 =
3433 2^{n(n+1)/2}|\GL(n,2)|,
3434 \]
3435 and
3436 \[
3437 |\Sp(2n,2)|
3438 =
3439 2^{n^2}\prod_{j=1}^n(2^{2j}-1).
3440 \]
3441 For $n=1,2,3$ this gives:
3442 \begin{center}
3443 \begin{tabular}{@{}rcc@{}}
3444 \toprule
3445 $n$&$|P_n|$&$|\Sp(2n,2)|$\\
3446 \midrule
3447 1&2&6\\
3448 2&48&720\\
3449 3&10,752&1,451,520\\
3450 \bottomrule
3451 \end{tabular}
3452 \end{center}
3453 These sizes permit exhaustive breadth-first or zero-one search through three qubits.
3454 
3455 \subsection{Total primitive count}
3456 \begin{computedbox}
3457 With every gate in $\mathcal S_P$ and $\mathcal S_C$ assigned unit cost and with SWAP excluded as a primitive, exhaustive search gives:
3458 \begin{center}
3459 \begin{tabular}{@{}rcccc@{}}
3460 \toprule
3461 $n$&restricted diameter&ambient diameter&defective targets&maximum defect\\
3462 \midrule
3463 1&1&3&0&0\\
3464 2&5&8&0&0\\
3465 3&8&12&24&1\\
3466 \bottomrule
3467 \end{tabular}
3468 \end{center}
3469 At $n=3$, six targets have distance pair $(7,6)$ and eighteen have pair $(8,7)$.
3470 \end{computedbox}
3471 
3472 Thus three qubits are the first total-count threshold in this exact swap-free model.
3473 
3474 \subsubsection{A three-qubit witness}
3475 One defective target has symplectic matrix
3476 \[
3477 M_3=
3478 \begin{pmatrix}
3479 0&1&0&0&0&0\\
3480 0&0&1&0&0&0\\
3481 1&0&0&0&0&0\\
3482 1&0&1&0&1&0\\
3483 0&1&0&0&0&1\\
3484 0&1&0&1&0&0
3485 \end{pmatrix}.
3486 \]
3487 A restricted word of length seven is
3488 \[
3489 \CX_{0\to2},
3490 \CZ_{12},
3491 \CX_{2\to0},
3492 \CX_{0\to2},
3493 \CX_{0\to1},
3494 \CX_{1\to0},
3495 \CX_{0\to1}.
3496 \]
3497 An ambient word of length six is
3498 \[
3499 H_1,
3500 \CX_{1\to2},
3501 \CX_{2\to1},
3502 \CX_{2\to0},
3503 \CX_{0\to2},
3504 H_0.
3505 \]
3506 
3507 \begin{figure}[ht]
3508 \centering
3509 \includegraphics[width=.98\textwidth]{assets/g_clifford_three_qubit_defect.pdf}
3510 \caption{A swap-free three-qubit parabolic target with total primitive-count defect one.}
3511 \label{g:fig:clifford-three}
3512 \end{figure}
3513 
3514 The Hadamards do not form a matched pair on the same wire.  They open and close the Lagrangian excursion in different coordinates.  This is a useful warning against assuming that every catalyst has the literal form $g\cdots g^{-1}$.
3515 
3516 \subsection{SWAP sensitivity}
3517 Add $\SWAP_{ij}$ to both alphabets as a unit-cost primitive.  The target groups remain unchanged, but the metric changes.
3518 
3519 \begin{computedbox}
3520 For $n=3$ with unit-cost SWAP gates, the restricted diameter drops from eight to seven, the ambient diameter drops from twelve to eleven, and every one of the $10,752$ parabolic targets has zero total-count defect.
3521 \end{computedbox}
3522 
3523 The preceding twenty-four defects therefore measure a real gate-alphabet distinction, not an invariant of the subgroup inclusion alone.  In many architectures SWAP is not elementary and costs three CNOTs, while in others qubit movement or relabeling changes the accounting.  The theorem must retain the convention.
3524 
3525 \subsection{Entangling-count defects}
3526 Now assign cost zero to $H_i$ and $S_i$ and cost one to $\CX$ and $\CZ$.
3527 
3528 \begin{computedbox}
3529 The exact censuses are:
3530 \begin{center}
3531 \begin{tabular}{@{}rccc@{}}
3532 \toprule
3533 $n$&defective targets&distance pairs&maximum defect\\
3534 \midrule
3535 1&0&none&0\\
3536 2&4&$(3,2)$ with multiplicity $4$&1\\
3537 3&1,624&
3538 $\begin{array}{c}
3539 (3,2):24,\ (4,3):432,\ (5,4):1056,\\
3540 (6,4):48,\ (6,5):64
3541 \end{array}$
3542 &2\\
3543 \bottomrule
3544 \end{tabular}
3545 \end{center}
3546 \end{computedbox}
3547 The entangling metric has an earlier threshold and a larger exceptional set.
3548 
3549 \subsubsection{A two-qubit witness}
3550 A canonical target is
3551 \[
3552 M_2=
3553 \begin{pmatrix}
3554 0&1&0&0\\
3555 1&0&0&0\\
3556 1&1&0&1\\
3557 1&1&1&0
3558 \end{pmatrix}.
3559 \]
3560 A restricted realization is
3561 \[
3562 \CX_{0\to1},
3563 S_1,
3564 \CX_{1\to0},
3565 \CX_{0\to1},
3566 \]
3567 with three entangling gates.  An ambient realization is
3568 \[
3569 H_1,
3570 \CX_{1\to0},
3571 \CX_{0\to1},
3572 H_0,
3573 S_1,
3574 S_0,
3575 \]
3576 with two entangling gates.
3577 
3578 \begin{figure}[ht]
3579 \centering
3580 \includegraphics[width=.98\textwidth]{assets/g_clifford_two_qubit_defect.pdf}
3581 \caption{A two-qubit entangling-count defect.  Local Clifford gates are free in this cost model.}
3582 \label{g:fig:clifford-two}
3583 \end{figure}
3584 
3585 \subsection{Census summary}
3586 \subsubsection{An analytic certificate for the four two-qubit defects}
3587 
3588 The four exceptional matrices admit one common lower-bound proof.  Work in the declared symplectic quotient and entangling metric, with $H_i$ and $S_i$ free and SWAP excluded as a primitive.  Put
3589 \[
3590 J_2=\begin{pmatrix}0&1\\1&0\end{pmatrix},
3591 \qquad D=\operatorname{diag}(d_0,d_1),
3592 \qquad d_0,d_1\in\F_2,
3593 \]
3594 and define
3595 \[
3596 M_D=\begin{pmatrix}J_2&0\\I_2+DJ_2&J_2\end{pmatrix}.
3597 \]
3598 
3599 \begin{theorem}[Two-qubit orbit and exact costs]\label{g:thm:clifford-two-analytic}
3600 Each of the four distinct matrices $M_D$ lies in $P_2$ and has restricted entangling cost three and ambient entangling cost two.  They form one orbit under left multiplication by the free restricted subgroup generated by $S_0,S_1$.
3601 \end{theorem}
3602 \begin{proof}
3603 The ambient sequence
3604 \[
3605 H_1,\ \CX_{1\to0},\ \CX_{0\to1},\ H_0
3606 \]
3607 has matrix $M_0=\left(\begin{smallmatrix}J_2&0\\I_2&J_2\end{smallmatrix}\right)$.  Applying $S_0^{d_0}S_1^{d_1}$ afterwards left multiplies by $\left(\begin{smallmatrix}I_2&0\\D&I_2\end{smallmatrix}\right)$ and gives $M_D$.  These matrices are distinct because $J_2$ is invertible.  This also proves their orbit statement and the ambient upper bound two.  The displayed restricted sequence for $M_2$ above gives $M_{I_2}$ using three CNOT gates and one free $S_1$.  Free final phase gates then give every $M_D$, proving the restricted upper bound three.
3608 
3609 For the restricted lower bound, the upper-left block of a parabolic product is the product of its upper-left blocks.  Each $S$ or CZ contributes $I_2$, while the two directed CNOTs contribute the elementary matrices
3610 \[
3611 L=\begin{pmatrix}1&0\\1&1\end{pmatrix},
3612 \qquad U=\begin{pmatrix}1&1\\0&1\end{pmatrix}.
3613 \]
3614 Products using at most two CNOTs belong to $\{I_2,L,U,LU,UL\}$, which does not contain $J_2$.  Thus any restricted circuit for $M_D$ requires at least three charged gates.
3615 
3616 For the ambient lower bound, reorder the coordinates as $(x_0,z_0\mid x_1,z_1)$.  A local Clifford acts by an invertible block-diagonal matrix in this order.  In $M_D$, each of the two diagonal $2\times2$ blocks is $\left(\begin{smallmatrix}0&0\\1&0\end{smallmatrix}\right)$ and has rank one.  In either directed CNOT or CZ, both diagonal blocks are $I_2$ and have rank two.  Left and right multiplication by local Cliffords preserve these diagonal-block ranks.  A circuit with one charged gate has the form $K_1 E K_2$ with $K_1,K_2$ local and $E$ a CNOT or CZ, so it cannot equal $M_D$.  A circuit with no charged gate is local and also has rank-two diagonal blocks.  The ambient cost is therefore at least two.
3617 \end{proof}
3618 
3619 The complete finite census finds exactly four defective targets.  Since the theorem supplies four distinct defective targets, it identifies the entire exceptional set in that census.  The exact costs and orbit description above have analytic proofs, while completeness of the finite classification retains the exhaustive-search evidence.
3620 
3621 \begin{figure}[ht]
3622 \centering
3623 \includegraphics[width=.76\textwidth]{assets/g_clifford_census.pdf}
3624 \caption{Exact parabolic-versus-ambient Clifford census. The vertical scale is symlogarithmic. At three qubits, adding SWAP as a unit-cost primitive removes all total-count defects.}
3625 \label{g:fig:clifford-census}
3626 \end{figure}
3627 
3628 The results establish three distinct lessons.
3629 \begin{enumerate}
3630 \item Basis escape produces genuine Clifford defects, not only linear CNOT defects.
3631 \item The first threshold depends on whether local gates are free.
3632 \item Adding a SWAP primitive can eliminate a finite total-count threshold.
3633 \end{enumerate}
3634 
3635 \subsection{Search completeness}
3636 The search state is the exact $2n\times2n$ binary symplectic matrix.  Every generator acts by a fixed row update.  Ordinary breadth-first search gives exact unit-cost distances.  Zero-one breadth-first search gives exact entangling costs.  Since every state of $P_n$ and $\Sp(2n,2)$ is reached, comparing the two distance maps is a complete census.
3637 
3638 The optimized C++ verifier represents a $6\times6$ matrix by a $36$-bit integer.  It enumerates the full three-qubit group in a few seconds in the present environment.  The Python implementation is slower but independently expresses the same state model.
3639 
3640 \subsection{Interpretation as symplectic holonomy}
3641 The parabolic subgroup is a fiber over the Lagrangian Grassmannian.  A Hadamard moves one coordinate out of the chosen Lagrangian.  The ambient path traverses other Lagrangian frames and returns to a target stabilizing $L_Z$.
3642 
3643 This is the symplectic analogue of the unitriangular Schreier loop.  The catalyst is a temporary exchange of $X$ and $Z$ roles.  The consumers are entangling gates that become cheaper in the changed frame.
3644 
3645 \subsection{CSS-preserving extensions}
3646 The parabolic model fixes one Lagrangian, but CSS circuit classes can be defined more narrowly or more broadly.  Possible restricted alphabets include:
3647 \begin{enumerate}
3648 \item CNOT and Pauli gates only,
3649 \item CNOT, $S$, and diagonal controlled phases,
3650 \item block-diagonal symplectic transformations preserving separate $X$ and $Z$ codes,
3651 \item logical Clifford gates preserving a CSS stabilizer decomposition,
3652 \item architecture-constrained versions of the preceding models.
3653 \end{enumerate}
3654 Each produces a different subgroup and metric.
3655 
3656 \begin{skeletonbox}
3657 A full CSS threshold paper should classify cost-preserving orbits of minimal defects, identify a symplectic-flag lower-bound invariant, and determine which defects survive when SWAP, qubit permutation, or local Cliffords are assigned alternative costs.
3658 \end{skeletonbox}
3659 
3660 \subsection{Depth and parallelism}
3661 Gate-count defects do not automatically imply depth defects.  Given a gate sequence, define its dependency graph and schedule commuting or disjoint gates in parallel.  The appropriate quantities are
3662 \[
3663 \Delta_{\mathrm{depth}}(U),
3664 \qquad
3665 \Delta_{\mathrm{2q-depth}}(U),
3666 \qquad
3667 \Delta_{\mathrm{space-time}}(U).
3668 \]
3669 A basis change applied transversally to many qubits may have small depth even when its total count is large.  Conversely, a two-gate count saving can increase depth under locality constraints.
3670 
3671 \subsection{Open Clifford problems}
3672 \begin{question}
3673 What are the defect orbits of the twenty-four three-qubit total-count targets under qubit permutations and parabolic conjugation?
3674 \end{question}
3675 \begin{question}
3676 Does the maximum parabolic-versus-Clifford defect grow linearly, as $n\log n$, or faster under total primitive count?
3677 \end{question}
3678 \begin{question}
3679 Can one prove a symbolic family with entangling-count defect greater than two, rather than relying on finite census data?
3680 \end{question}
3681 \begin{question}
3682 Which finite symplectic parabolics are geodesically convex after SWAP is included as a primitive?
3683 \end{question}
3684 \begin{conjecturebox}
3685 The observed three-qubit defects should admit a small collection of symplectic root motifs analogous to the three-cross, one-phase classification in the unitriangular case.  The present monograph records the exact census and witnesses but does not claim that classification.
3686 \end{conjecturebox}
3687 
3688 \section{Temporary nonlinearity: affine logic versus Toffoli-assisted synthesis}\label{g:ch:affine-toffoli}
3689 \index{Toffoli gate}
3690 \index{affine reversible circuit}
3691 \index{temporary nonlinearity}
3692 \index{algebraic normal form}
3693 
3694 
3695 \subsection{The question}
3696 Let
3697 \[
3698 \operatorname{AGL}(n,2)
3699 =
3700 \{x\mapsto Ax+b:A\in\GL(n,2),\ b\in\F_2^n\}
3701 \]
3702 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.
3703 
3704 The catalytic question is:
3705 \begin{quote}
3706 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?
3707 \end{quote}
3708 This is the nonlinear analogue of dirty linear memory.
3709 
3710 \subsection{Algebraic normal form}
3711 Every Boolean coordinate function has a unique algebraic normal form
3712 \[
3713 f_i(x)
3714 =
3715 \bigoplus_{S\subseteq[n]}a_{i,S}\prod_{j\in S}x_j.
3716 \]
3717 Affine maps have degree at most one.  A Toffoli gate targeting $t$ with controls $a,b$ performs
3718 \[
3719 x_t\longmapsto x_t+x_ax_b,
3720 \]
3721 which can raise the degree of later coordinates.  The final affine target requires every higher-degree coefficient to cancel.
3722 
3723 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:
3724 \begin{itemize}
3725 \item the dimension of the quadratic monomial span,
3726 \item directional derivatives $D_u f(x)=f(x+u)+f(x)$,
3727 \item the rank of the bilinear polarization,
3728 \item the number of outputs consuming a nonlinear workspace term,
3729 \item restoration obligations for every nonlinear carrier.
3730 \end{itemize}
3731 
3732 \subsection{Exact three-bit census}
3733 On three bits,
3734 \[
3735 |\operatorname{AGL}(3,2)|
3736 =2^3|\GL(3,2)|
3737 =1344,
3738 \]
3739 while the group generated by NOT, CNOT, and Toffoli is the full permutation group
3740 \[
3741 S_8,
3742 \qquad |S_8|=40320.
3743 \]
3744 Both spaces can be enumerated exactly.
3745 
3746 \begin{computedbox}
3747 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:
3748 \begin{enumerate}
3749 \item total primitive gate count, where NOT, CNOT, and Toffoli cost one,
3750 \item entangling count, where NOT is free and CNOT and Toffoli cost one.
3751 \end{enumerate}
3752 There are no defective affine targets among all $1344$ targets.
3753 \end{computedbox}
3754 
3755 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.
3756 
3757 \begin{figure}[ht]
3758 \centering
3759 \includegraphics[width=.84\textwidth]{assets/g_affine_toffoli_census.pdf}
3760 \caption{The complete three-bit affine-versus-Toffoli census is rigid.}
3761 \label{g:fig:affine-toffoli-census}
3762 \end{figure}
3763 
3764 \subsection{Interpretation of the negative result}
3765 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.
3766 
3767 The negative result is valuable for three reasons.
3768 \begin{enumerate}
3769 \item It gives a certified lower threshold: any total- or entangling-count defect requires at least four bits.
3770 \item It prevents a forced analogy with the six-wire linear catalyst.
3771 \item It supplies a complete regression test for future synthesis code.
3772 \end{enumerate}
3773 
3774 \subsection{A formal nonlinear catalyst}
3775 A clean one-workspace template is
3776 \[
3777 T\;h_m\cdots h_1\;T^{-1},
3778 \]
3779 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.
3780 
3781 \begin{figure}[ht]
3782 \centering
3783 \includegraphics[width=.96\textwidth]{assets/g_temporary_nonlinearity_skeleton.pdf}
3784 \caption{A temporary-nonlinearity template.  It is a search skeleton, not a proved shortcut.}
3785 \label{g:fig:nonlinear-skeleton}
3786 \end{figure}
3787 
3788 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.
3789 
3790 \subsection{Conjugation formulas}
3791 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,
3792 \[
3793 T_{ab\to t}X_tT_{ab\to t}=X_t,
3794 \]
3795 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.
3796 
3797 A systematic search should classify pairs $(T,h)$ for which
3798 \[
3799 ThT^{-1}\in\operatorname{AGL}(n,2).
3800 \]
3801 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.
3802 
3803 \subsection{Potential lower-bound invariants}
3804 \subsubsection{Quadratic support debt}
3805 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.
3806 
3807 \subsubsection{Derivative rank}
3808 For an affine map, every derivative $D_u f$ is constant.  During a nonlinear excursion, the derivative map
3809 \[
3810 u\mapsto D_u f(x)
3811 \]
3812 can depend on $x$.  One can track the dimension of the nonconstant derivative space and require it to return to zero.
3813 
3814 \subsubsection{Higher-order Möbius coefficients}
3815 The ANF coefficients are the Möbius transform of the truth table.  Projectors onto degree layers give an exact packet decomposition
3816 \[
3817 f=f^{(0)}+f^{(1)}+f^{(2)}+\cdots.
3818 \]
3819 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.
3820 
3821 \subsection{Four-bit search architecture}
3822 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.
3823 \begin{enumerate}
3824 \item Meet in the middle for a fixed candidate target and length.
3825 \item SAT or SMT encoding of a length-$L$ circuit with affine endpoint constraints.
3826 \item Bidirectional search restricted to states within a bounded nonlinear-degree or Toffoli-count budget.
3827 \item Enumeration of two- or four-Toffoli normal forms modulo affine conjugation.
3828 \item Mixed-integer or algebraic solving of ANF coefficient equations.
3829 \end{enumerate}
3830 
3831 \begin{protocol}[First four-bit threshold search]
3832 \begin{enumerate}
3833 \item Compute exact affine distances for all $322{,}560$ affine targets.
3834 \item Enumerate ambient words with two Toffoli gates modulo affine gates on the left and right.
3835 \item Retain words whose endpoint is affine.
3836 \item Compare with the exact affine distance.
3837 \item If no defect appears, increase the Toffoli budget and produce an unsatisfiability certificate for every shorter length.
3838 \end{enumerate}
3839 \end{protocol}
3840 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.
3841 
3842 \subsection{Resource variants}
3843 Temporary nonlinearity may be useful under one metric and useless under another.  Natural costs include:
3844 \[
3845 \begin{gathered}
3846 \text{Toffoli count},\quad \text{CNOT count},\quad
3847 T\text{-count after decomposition},\quad T\text{-depth},\\
3848 \text{ancilla count},\quad \text{total depth}.
3849 \end{gathered}
3850 \]
3851 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.
3852 
3853 \subsection{Related nonlinear gate families}
3854 The same program applies to:
3855 \begin{itemize}
3856 \item CCZ-assisted diagonal Boolean phase maps,
3857 \item relative-phase Toffoli gates,
3858 \item multi-controlled $X$ and $Z$ gates,
3859 \item Reed--Muller degree hierarchies,
3860 \item reversible arithmetic over $\Z_d$,
3861 \item polynomial automorphisms over finite rings.
3862 \end{itemize}
3863 
3864 \begin{conjecturebox}
3865 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.
3866 \end{conjecturebox}
3867 
3868 \subsection{Reproducible code}
3869 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.
3870 
3871 \begin{lstlisting}[style=pythonstyle,caption={Exact three-bit affine-versus-Toffoli census.}]
3872 from catalytic_gate_atlas import exact_affine_toffoli_census
3873 
3874 print(exact_affine_toffoli_census(3, entangling_cost=False))
3875 print(exact_affine_toffoli_census(3, entangling_cost=True))
3876 \end{lstlisting}
3877 The expected defect count is zero in both outputs.
3878 
3879 \section{Phase-polynomial and Clifford+\texorpdfstring{$T$}{T} catalysis}\label{g:ch:phase-cliffordt}
3880 \index{Clifford+T circuit}
3881 \index{phase polynomial}
3882 \index{T-count}
3883 \index{T-depth}
3884 \index{Pareto defect}
3885 
3886 
3887 \subsection{Why the phase setting is different}
3888 Fault-tolerant quantum compilation rarely assigns equal cost to every gate.  Clifford operations are often treated as inexpensive relative to non-Clifford gates, while connectivity and parity computation can dominate the remaining cost.  Consequently there is no single Clifford+$T$ defect.  One must specify at least
3889 \[
3890 \mathbf c(U)=
3891 \bigl(
3892 T\text{-count},
3893 T\text{-depth},
3894 \text{two-qubit count},
3895 \text{two-qubit depth},
3896 \text{ancillas}
3897 \bigr).
3898 \]
3899 A catalytic excursion may improve one component and worsen another.  The natural comparison is therefore Pareto-valued rather than scalar unless a hardware-specific weight vector is fixed.
3900 
3901 Let $\omega=e^{i\pi/4}$.  A phase-polynomial circuit on $n$ qubits has the form \cite{g:AmyMosca2019,g:Selinger2013}
3902 \begin{equation}\label{g:eq:phase-poly-normal}
3903 U\ket{x}=\omega^{P(x)}\ket{Ax+b},
3904 \end{equation}
3905 where $A\in\GL(n,2)$, $b\in\F_2^n$, and $P:\F_2^n\to\Z_8$ is represented as a sum of binary linear forms with coefficients in $\Z_8$.  The diagonal case has $A=I$ and $b=0$.
3906 
3907 The restricted model may be chosen in several ways:
3908 \begin{enumerate}
3909 \item diagonal phase gadgets only;
3910 \item CNOT-dihedral circuits generated by $X$, CNOT, and $T$;
3911 \item parity networks in which every intermediate transformation remains affine on computational basis labels;
3912 \item a prescribed family of commuting Pauli rotations.
3913 \end{enumerate}
3914 The ambient model may add Hadamards, arbitrary Clifford conjugations, measurements, or ancillas.  These choices define different problems.
3915 
3916 \subsection{Pauli-rotation language}
3917 For a Pauli operator $P$ and angle $\theta$, write
3918 \[
3919 R_P(\theta)=e^{-i\theta P/2}.
3920 \]
3921 Every Clifford $C$ satisfies
3922 \begin{equation}\label{g:eq:pauli-conjugation}
3923 C R_P(\theta) C^\dagger=R_{CPC^\dagger}(\theta).
3924 \end{equation}
3925 Thus a short ambient basis change can rotate a large family of phase gadgets into a different commuting or nearly commuting family, apply them there, and rotate back.
3926 
3927 \begin{provedbox}
3928 Equation \eqref{g:eq:pauli-conjugation} is an exact catalytic transport identity.  It does not by itself prove a gate-count defect.  A defect additionally requires a lower bound showing that the transported family is more expensive in the restricted representation than the opening and closing Clifford layers plus the transported implementation.
3929 \end{provedbox}
3930 
3931 The simplest symbolic sandwich is
3932 \[
3933 C\left(\prod_{j=1}^m R_{P_j}(\theta_j)\right)C^\dagger
3934 =
3935 \prod_{j=1}^m R_{CP_jC^\dagger}(\theta_j).
3936 \]
3937 If the $P_j$ commute, their conjugates commute.  A catalyst can therefore change the geometry of the support without changing the algebra of the angles.
3938 
3939 \subsection{Phase polynomials and parity carriers}
3940 A CNOT network computes linear parities
3941 \[
3942 \lambda(x)=a\cdot x\in\F_2.
3943 \]
3944 Applying $T^k$ to a wire carrying $\lambda(x)$ contributes
3945 \[
3946 \omega^{k\lambda(x)}
3947 \]
3948 to the phase polynomial.  A parity network must create each required parity, expose it to a phase gate, and restore the linear map required at the endpoint.
3949 
3950 This makes phase-polynomial synthesis a close relative of the snapshot families in the linear core.  A parity row may evolve through
3951 \[
3952 \lambda_0,\lambda_1,\ldots,\lambda_m,
3953 \]
3954 with selected states consumed by phase gates.  The difference is that consumption need not copy the parity to another row; it can deposit phase while leaving the carrier unchanged.
3955 
3956 \begin{skeletonbox}
3957 A candidate phase catalyst consists of:
3958 \begin{enumerate}
3959 \item a Clifford $C$ that opens a non-diagonal frame;
3960 \item an evolving Pauli or parity carrier in that frame;
3961 \item several phase rotations consuming intermediate carrier states;
3962 \item $C^\dagger$ restoring the original diagonal or CNOT-dihedral model;
3963 \item a certificate that no restricted parity network attains the same resource vector.
3964 \end{enumerate}
3965 \end{skeletonbox}
3966 
3967 \begin{figure}[ht]
3968 \centering
3969 \includegraphics[width=.94\textwidth]{assets/g_phase_polynomial_skeleton.pdf}
3970 \caption{Symbolic Clifford+$T$ catalyst: a basis excursion transports a family of phase obligations and is removed at the endpoint.}
3971 \label{g:fig:phase-polynomial-skeleton}
3972 \end{figure}
3973 
3974 \subsection{\texorpdfstring{$T$}{T}-count as a coding problem}
3975 For diagonal Clifford+$T$ synthesis without ancillas, equivalent phase-polynomial descriptions can differ by identities whose coefficients vanish modulo eight on Boolean inputs.  Minimizing the number of odd coefficients is naturally expressed as a coset-decoding problem in a punctured Reed--Muller-type code.
3976 
3977 Let $a\in\Z_8^{2^n-1}$ index nonzero linear forms and let $\operatorname{odd}(a)$ denote the binary vector recording which coefficients are odd.  An abstract restricted $T$-count is
3978 \[
3979 \ell_T(P)=
3980 \min_{a:\,P_a=P}
3981 \operatorname{wt}(\operatorname{odd}(a)).
3982 \]
3983 An ambient Clifford excursion changes not only the coefficient vector but also the Pauli frame in which the rotations are represented.  A lower bound that survives ambient Clifford conjugation must therefore be invariant under the relevant symplectic action or must explicitly charge the frame change.
3984 
3985 \subsection{\texorpdfstring{$T$}{T}-depth and commuting layers}
3986 Two phase gadgets may share a $T$ layer when a suitable Clifford network maps their parities to distinct wires or when ancilla resources permit parallel extraction.  Define the conflict graph $\Gamma_P$ whose vertices are odd phase terms and whose edges encode inability to realize two terms in one layer under the chosen ancilla and connectivity rules.  Then
3987 \[
3988 T\text{-depth}(P)\ge\chi(\Gamma_P)
3989 \]
3990 for any conflict graph whose edge relation is sound.  Catalysis can alter $\Gamma_P$ by changing the Pauli frame.  The right question is not merely whether $C$ preserves the number of terms, but whether it reduces the chromatic or scheduling obstruction enough to repay its own depth.
3991 
3992 \subsection{A vector-valued defect}
3993 For a target $U$ in a restricted phase model, define
3994 \[
3995 \mathcal C_{\mathrm{res}}(U)
3996 =
3997 \{\mathbf c(\mathcal W):\mathcal W\text{ is a restricted circuit for }U\}
3998 \]
3999 and similarly $\mathcal C_{\mathrm{amb}}(U)$.  Their Pareto frontiers are denoted $\operatorname{Pareto}_{\mathrm{res}}(U)$ and $\operatorname{Pareto}_{\mathrm{amb}}(U)$.
4000 
4001 \begin{definition}[Pareto catalytic defect]
4002 A target has a Pareto catalytic defect when the ambient Pareto frontier contains a point strictly dominating every restricted cost vector in at least one declared region of resource space.
4003 \end{definition}
4004 
4005 Scalarization by positive weights $w$ gives
4006 \[
4007 \Delta_w(U)=
4008 \min_{c\in\mathcal C_{\mathrm{res}}(U)}w\cdot c
4009 -
4010 \min_{c\in\mathcal C_{\mathrm{amb}}(U)}w\cdot c.
4011 \]
4012 Different $w$ can change the magnitude of the defect and whether it is zero or positive.  It remains nonnegative because every restricted realization is also an ambient realization with the same resource vector.
4013 
4014 \subsection{Exact finite-search model}
4015 A finite exact atlas can be built \cite{g:KliuchnikovEtAl2013,g:AmyEtAl2013} for small $n$ by representing Clifford+$T$ operators in one of three ways.
4016 \begin{enumerate}
4017 \item Exact matrices over the cyclotomic ring $\Z[1/\sqrt2,i]$ modulo global phase.
4018 \item Normal forms combining a binary symplectic Clifford with a phase-polynomial record.
4019 \item Quotients by left and right Clifford actions when only $T$-count is charged.
4020 \end{enumerate}
4021 The third model can be dramatically smaller but requires care: quotienting is sound only when the free Clifford actions in the cost model agree with the quotient relation.
4022 
4023 \begin{protocol}[Small-width Clifford+$T$ threshold atlas]
4024 \begin{enumerate}
4025 \item Fix exact versus approximate synthesis, ancilla rules, and the resource vector.
4026 \item Enumerate the restricted target subgroup or a complete set of normal forms.
4027 \item Compute restricted Pareto frontiers by multiobjective shortest path.
4028 \item Enumerate ambient states or use meet in the middle for candidate targets.
4029 \item Store an optimal witness and a lower-bound certificate for every defect.
4030 \item Classify defects under qubit permutation and free Clifford equivalence.
4031 \end{enumerate}
4032 \end{protocol}
4033 
4034 \subsection{Lower-bound candidates}
4035 \subsubsection{Odd-support rank}
4036 The span of odd phase terms is invariant under some restricted rewrites but transforms covariantly under linear changes of variables.  Its dimension gives a coarse obstruction.
4037 
4038 \subsubsection{Pauli support geometry}
4039 Represent a commuting Pauli family by an isotropic subspace of $\F_2^{2n}$.  Restricted diagonal circuits remain in the $Z$ Lagrangian.  Ambient Clifford circuits move through the symplectic Grassmannian.  Distance from the $Z$ Lagrangian, together with the number of deposited rotations, is the phase analogue of microscopic flag escape.
4040 
4041 \subsubsection{Moment and derivative packets}
4042 For a phase function $P$, finite differences
4043 \[
4044 D_uP(x)=P(x+u)-P(x)\pmod8
4045 \]
4046 separate affine, quadratic, and higher interactions.  A hierarchy of derivative tensors can record temporary flow into nonlinear phase packets.
4047 
4048 \subsubsection{Architecture-aware parity rank}
4049 On a coupling graph, each parity has a Steiner cost.  A catalyst can be profitable by making several required parities share a Steiner tree.  A sound lower bound may combine cut rank with edge congestion and restoration debt.
4050 
4051 \subsection{Tensor and repeated-module questions}
4052 For targets $U$ and $V$, independent synthesis gives
4053 \[
4054 \ell_T(U\otimes V)
4055 \le
4056 \ell_T(U)+\ell_T(V)
4057 \]
4058 when the systems are disjoint and local Clifford cost is ignored.  Joint synthesis may be better because phase identities can couple terms across modules.  This motivates a stable regularization
4059 \[
4060 \tau_T(U)=
4061 \liminf_{r\to\infty}
4062 \frac{\ell_T(U^{\otimes r})}{r}.
4063 \]
4064 A one-copy rigid phase target could still display tensor activation.
4065 
4066 \begin{conjecturebox}
4067 There are diagonal or CNOT-dihedral targets whose Pareto frontier is strictly improved by a restored non-diagonal Clifford excursion.  The smallest qubit threshold and the resource component in which the first defect appears are open in this monograph.
4068 \end{conjecturebox}
4069 
4070 \subsection{What would count as a theorem}
4071 A publishable first result in this direction should contain all of the following:
4072 \begin{enumerate}
4073 \item an exact target family and gate alphabets;
4074 \item explicit ambient circuits;
4075 \item a restricted lower bound for the same declared cost;
4076 \item exact treatment of global phase and ancillas;
4077 \item classification below the first threshold or a proof of minimality;
4078 \item reproducible symbolic code.
4079 \end{enumerate}
4080 Merely rewriting a phase gadget with Hadamards is not sufficient.  The decisive content is the optimality comparison.
4081 
4082 \section{Gaussian, matchgate, and fermionic catalytic models}\label{g:ch:gaussian}
4083 \index{Gaussian circuit}
4084 \index{matchgate}
4085 \index{Bogoliubov transformation}
4086 \index{fermionic Gaussian circuit}
4087 \index{symplectic embedding}
4088 
4089 
4090 \subsection{Two Gaussian settings}
4091 Quantum Gaussianity occurs \cite{g:WeedbrookEtAl2012} in two closely related but algebraically different settings.
4092 
4093 For $n$ bosonic modes, a Gaussian unitary acts on quadratures
4094 \[
4095 \mathbf r=(q_1,\ldots,q_n,p_1,\ldots,p_n)^T
4096 \]
4097 by an affine symplectic transformation
4098 \[
4099 \mathbf r\longmapsto S\mathbf r+d,
4100 \qquad
4101 S\in\Sp(2n,\R).
4102 \]
4103 For $n$ fermionic modes, a fermionic Gaussian unitary acts on $2n$ Majorana operators by
4104 \[
4105 \gamma\longmapsto O\gamma,
4106 \qquad O\in SO(2n).
4107 \]
4108 Nearest-neighbor matchgates give a circuit presentation of a fermionic Gaussian subgroup on qubits.
4109 
4110 In both cases one can choose a restricted subgroup preserving a flag, mode ordering, particle number, or bipartition, and compare it with a larger Gaussian or non-Gaussian gate set.
4111 
4112 \subsection{An inherited symplectic shear theorem}
4113 Every invertible linear transformation $A\in\GL(n,R)$ has a canonical symplectic embedding
4114 \begin{equation}\label{g:eq:symplectic-embedding}
4115 \iota(A)=
4116 \begin{pmatrix}
4117 A&0\\
4118 0&A^{-T}
4119 \end{pmatrix}.
4120 \end{equation}
4121 Indeed, with
4122 \[
4123 J=
4124 \begin{pmatrix}0&I\\-I&0\end{pmatrix},
4125 \]
4126 one checks
4127 \[
4128 \iota(A)^T J\iota(A)=J.
4129 \]
4130 Thus every row-transvection identity in the established linear theory induces an exact identity between symplectic shear circuits.
4131 
4132 \begin{provedbox}
4133 Under a Gaussian gate alphabet in which each embedded elementary transvection $\iota(I+aE_{ij})$ is one primitive and direction is the only restriction, the universal six-row catalytic atom embeds into a twelve-quadrature Gaussian atom with restricted length seven and ambient length six.
4134 \end{provedbox}
4135 
4136 This is a formal inheritance statement for the declared shear alphabet.  It does not assert optimality after arbitrary beam splitters, squeezers, Fourier transforms, or local Gaussian gates are admitted at unit cost.
4137 
4138 \begin{figure}[ht]
4139 \centering
4140 \includegraphics[width=.94\textwidth]{assets/g_gaussian_shear_catalysis.pdf}
4141 \caption{The row-transvection atom embedded as a Gaussian symplectic shear circuit.}
4142 \label{g:fig:gaussian-shear}
4143 \end{figure}
4144 
4145 \subsection{Bosonic gate hierarchies}
4146 Natural nested models include
4147 \[
4148 \text{triangular shears}
4149 \subset
4150 \text{all Gaussian unitaries}
4151 \subset
4152 \text{Gaussian plus a non-Gaussian primitive}
4153 \subset
4154 U(\mathcal H).
4155 \]
4156 Typical primitive resources are:
4157 \begin{itemize}
4158 \item SUM or controlled displacement gates,
4159 \item beam splitters,
4160 \item single-mode and two-mode squeezers,
4161 \item Fourier transforms,
4162 \item cubic phase gates,
4163 \item photon counting or non-Gaussian state injection.
4164 \end{itemize}
4165 Each inclusion supports a different defect.  A target Gaussian transformation might be shortened by leaving a triangular decomposition but remaining Gaussian.  A more radical question asks whether temporary non-Gaussianity can shorten a final Gaussian target.
4166 
4167 \subsection{Bloch--Messiah versus catalytic synthesis}
4168 A bosonic Gaussian unitary admits a Bloch--Messiah decomposition
4169 \[
4170 S=K_1 D K_2,
4171 \]
4172 where $K_1,K_2$ are passive symplectic transformations and $D$ is a diagonal squeezing layer.  This normal form optimizes conceptual structure, not necessarily a weighted gate count on a specific architecture.
4173 
4174 Catalytic synthesis asks whether a short excursion into a basis where many shear or squeezing obligations align can reduce total cost.  The opening and closing passive layers play the role of the catalyst.
4175 
4176 \begin{skeletonbox}
4177 A Gaussian catalytic theorem requires:
4178 \begin{enumerate}
4179 \item a declared primitive library and cost vector;
4180 \item a target subgroup, such as triangular, number conserving, or local;
4181 \item an explicit sandwich $KHK^{-1}$ returning to the target subgroup;
4182 \item a lower bound based on symplectic rank, singular values, graph cuts, or mode support;
4183 \item treatment of approximation error when continuous parameters are synthesized numerically.
4184 \end{enumerate}
4185 \end{skeletonbox}
4186 
4187 \subsection{Fermionic Gaussian and matchgate circuits}
4188 Let $c_j,c_j^\dagger$ be fermionic creation and annihilation operators.  Quadratic Hamiltonians generate Gaussian unitaries, and their action is determined by an orthogonal transformation on Majoranas.  Number-conserving Gaussian operations correspond to a unitary action on modes, while general Gaussian operations allow particle-hole mixing.
4189 
4190 This yields the hierarchy
4191 \[
4192 \begin{gathered}
4193 U(n)\text{ mode transformations}
4194 \subset SO(2n)\text{ fermionic Gaussian transformations}\\
4195 \subset \text{parity-preserving unitaries}.
4196 \end{gathered}
4197 \]
4198 A temporary Bogoliubov transformation can violate number conservation while preserving parity.  The target may nevertheless return to the number-conserving subgroup.
4199 
4200 \begin{definition}[Bogoliubov catalytic defect]
4201 For a number-conserving Gaussian target $U$, compare the minimum cost using number-conserving primitives with the minimum cost using general Gaussian primitives, requiring the endpoint to conserve number exactly.
4202 \end{definition}
4203 
4204 \subsection{Matchgates and geometry}
4205 Nearest-neighbor matchgate circuits \cite{s:Valiant2002,s:JozsaMiyake2008} have strong classical simulation properties.  Their geometry changes when SWAP, fermionic SWAP, long-range connectivity, or a single non-matchgate resource is added.  Candidate restricted/ambient pairs include:
4206 \begin{enumerate}
4207 \item nearest-neighbor matchgates versus all-to-all matchgates;
4208 \item number-conserving matchgates versus general matchgates;
4209 \item matchgates versus parity-preserving two-qubit gates;
4210 \item Gaussian circuits versus Gaussian circuits with one reusable non-Gaussian ancilla.
4211 \end{enumerate}
4212 
4213 A compiler application is immediate: a temporary mode permutation or particle-hole rotation may allow a batch of otherwise expensive interactions to share one routing or basis-change layer.
4214 
4215 \subsection{Covariance-matrix lower bounds}
4216 For a Gaussian state, the covariance matrix $\Gamma$ transforms as
4217 \[
4218 \Gamma\longmapsto S\Gamma S^T
4219 \]
4220 in the bosonic case and
4221 \[
4222 \Gamma\longmapsto O\Gamma O^T
4223 \]
4224 in the fermionic case.  Possible restricted lower bounds include:
4225 \begin{itemize}
4226 \item rank change of off-diagonal covariance blocks,
4227 \item symplectic singular-value obligations,
4228 \item growth of mode support,
4229 \item graph bandwidth and cut rank,
4230 \item number of nontrivial canonical angles between invariant subspaces.
4231 \end{itemize}
4232 One elementary gate changes only a controlled portion of these data.  A useful invariant must also charge preparation of a carrier that makes progress on many cuts simultaneously.
4233 
4234 \subsection{Temporary non-Gaussianity}
4235 Suppose a non-Gaussian primitive $g$ is introduced and later removed:
4236 \[
4237 U=g h_m\cdots h_1 g^{-1},
4238 \qquad U\in G_{\mathrm{Gauss}}.
4239 \]
4240 If $g h_i g^{-1}$ generates several useful Gaussian effects, the excursion may be catalytic.  However, many standard non-Gaussianity monotones vanish only on states rather than unitaries, and cancellation at the endpoint complicates direct lower bounds.
4241 
4242 Candidate monotones and certificates include:
4243 \begin{itemize}
4244 \item degree in the Weyl characteristic function,
4245 \item Wigner negativity generated during the path,
4246 \item operator Schmidt rank across mode cuts,
4247 \item polynomial degree of Heisenberg-evolved quadratures,
4248 \item stabilizer rank for encoded finite-dimensional subspaces.
4249 \end{itemize}
4250 
4251 \subsection{Exact and numerical search}
4252 Finite exact enumeration is available for binary symplectic or orthogonal quotients, but continuous Gaussian groups require a different strategy.
4253 \begin{enumerate}
4254 \item Fix a symbolic gate skeleton and solve polynomial equations for parameters.
4255 \item Use interval arithmetic to certify nonexistence below a length.
4256 \item Exploit canonical decompositions to quotient local or passive layers.
4257 \item For discrete-angle Gaussian libraries, use exact algebraic-number arithmetic.
4258 \item Store both an upper-bound circuit and a dual or algebraic certificate.
4259 \end{enumerate}
4260 
4261 \subsection{Architecture and routing}
4262 On a line or grid, Gaussian and matchgate circuits may be dominated by routing.  Let $G_{\mathrm{conn}}$ be the hardware graph.  A mode permutation $\pi$ can be treated as a catalyst if it is opened, many interactions are executed in the reordered frame, and $\pi^{-1}$ restores the logical labeling.  The benefit is
4263 \[
4264 \text{routing saved across consumers}
4265 -
4266 2\,\text{cost}(\pi).
4267 \]
4268 This is the same amortization law as the linear snapshot family, now applied to mode geometry.
4269 
4270 \begin{conjecturebox}
4271 There exist number-conserving or nearest-neighbor Gaussian targets whose minimum weighted cost is reduced by a restored Bogoliubov, mode-permutation, or non-Gaussian excursion.  The first exact threshold depends on the primitive library and is not determined here.
4272 \end{conjecturebox}
4273 
4274 \subsection{Research deliverables}
4275 A complete Gaussian extension should produce:
4276 \begin{enumerate}
4277 \item a finite or semialgebraic model with exact endpoint equality;
4278 \item at least one nontrivial lower-bound invariant;
4279 \item a minimal catalytic atom;
4280 \item a weighted hardware interpretation;
4281 \item a tensor or repeated-mode amplification theorem;
4282 \item code using exact arithmetic or certified intervals.
4283 \end{enumerate}
4284 
4285 \section{Symmetry, ancillas, measurement, and architecture}\label{g:ch:symmetry-measurement}
4286 \index{symmetry-preserving circuit}
4287 \index{ancilla}
4288 \index{measurement and feedforward}
4289 \index{architecture constraint}
4290 \index{resource theory}
4291 
4292 
4293 \subsection{Beyond subgroup word metrics}
4294 Some of the most important quantum resource enlargements are not inclusions of groups.  Measurement introduces branches, reset is irreversible, and ancillas enlarge the Hilbert space.  The appropriate abstraction is a nested pair of realization categories
4295 \[
4296 \mathcal C_{\mathrm{res}}
4297 \subseteq
4298 \mathcal C_{\mathrm{amb}},
4299 \]
4300 with a cost assigned to generating morphisms.
4301 
4302 For a target channel $\Phi$ in the restricted category, define
4303 \[
4304 c_{\mathrm{res}}(\Phi)
4305 =
4306 \inf\{\cost(W):W\text{ realizes }\Phi\text{ in }\mathcal C_{\mathrm{res}}\}
4307 \]
4308 and similarly $c_{\mathrm{amb}}(\Phi)$.  The value $+\infty$ is allowed.  A finite positive difference is a metric defect; an infinite difference is an existence defect.
4309 
4310 \subsection{Symmetry-preserving circuits}
4311 Let $Q$ be a conserved charge and let
4312 \[
4313 H_Q=\{U:[U,Q]=0\}.
4314 \]
4315 Restricted circuits use gates commuting with $Q$.  Ambient circuits may temporarily leave $H_Q$ but must return to a charge-preserving endpoint.
4316 
4317 Examples include:
4318 \begin{itemize}
4319 \item particle-number conservation,
4320 \item parity conservation,
4321 \item total spin or magnetization,
4322 \item lattice gauge constraints,
4323 \item stabilizer or CSS sector preservation,
4324 \item block-diagonal representation sectors.
4325 \end{itemize}
4326 
4327 The Hilbert space decomposes as
4328 \[
4329 \mathcal H=\bigoplus_q\mathcal H_q.
4330 \]
4331 A restricted circuit is block diagonal.  An ambient catalyst may couple sectors, use the enlarged route, and decouple them at the endpoint.
4332 
4333 \begin{skeletonbox}
4334 A symmetry-breaking catalyst has three obligations:
4335 \begin{enumerate}
4336 \item quantify how far the path leaves the symmetry algebra;
4337 \item prove exact return, not merely return on a chosen input state;
4338 \item compare the cost with every symmetry-preserving realization of the full target operator.
4339 \end{enumerate}
4340 \end{skeletonbox}
4341 
4342 \subsection{Sector-flow invariants}
4343 Let $P_q$ be the projector onto sector $q$.  For an intermediate unitary $U_t$, define transfer blocks
4344 \[
4345 T_{q,r}(t)=P_q U_t P_r.
4346 \]
4347 A restricted path has $T_{q,r}=0$ for $q\ne r$.  Ambient paths may populate off-diagonal blocks.  Possible excursion measures include
4348 \[
4349 \sum_{q\ne r}\rank T_{q,r},
4350 \qquad
4351 \max_{q\ne r}\|T_{q,r}\|,
4352 \qquad
4353 \text{bandwidth in }|q-r|.
4354 \]
4355 These are analogues of strict-upper rank and bandwidth in the unitriangular theory.
4356 
4357 \subsection{Clean and dirty ancillas}
4358 A clean ancilla starts in a specified state, usually $\ket0$, and must be returned to that state.  A dirty ancilla starts in an unknown state and must be restored for every input.
4359 
4360 Let $U$ act on the data register.  A clean-ancilla realization is a unitary $W$ satisfying
4361 \[
4362 W(\ket\psi\otimes\ket0)
4363 =(U\ket\psi)\otimes\ket0
4364 \quad\text{for every }\ket\psi.
4365 \]
4366 A dirty-ancilla realization requires
4367 \[
4368 W(\ket\psi\otimes\ket\phi)
4369 =(U\ket\psi)\otimes\ket\phi
4370 \quad\text{for every }\ket\psi,\ket\phi.
4371 \]
4372 The second condition is strictly stronger.
4373 
4374 Ancillas define a family of defects
4375 \[
4376 \Delta_{a,\mathrm{clean}}(U),
4377 \qquad
4378 \Delta_{a,\mathrm{dirty}}(U),
4379 \]
4380 where $a$ is the number of ancillary qubits or modes.  Stable ancilla capacity asks whether a fixed number of reusable ancillas can yield an unbounded saving as the data size grows.
4381 
4382 \subsection{Measurement and feedforward}
4383 A measurement-assisted realization is described by an instrument with classical outcomes $m$, conditional channels $\Phi_m$, and feedforward operations.  Exact deterministic implementation of a unitary target requires every branch, after correction, to induce the same channel.
4384 
4385 The cost vector may include
4386 \[
4387 (
4388 T\text{-count},
4389 \text{two-qubit count},
4390 \text{measurement rounds},
4391 \text{classical latency},
4392 \text{ancilla qubits}
4393 ).
4394 \]
4395 A measurement can create an existence defect by realizing a channel unavailable unitarily under the same locality or depth constraints, or a metric defect by reducing one resource while increasing another.
4396 
4397 \begin{definition}[Branch-catalytic realization]
4398 A measurement-assisted circuit is branch catalytic when the intermediate classical or quantum branch information is absent from the final data channel and all declared work systems are reset or discarded according to the model.
4399 \end{definition}
4400 
4401 \subsection{Teleportation as a canonical ambient excursion}
4402 Gate teleportation replaces direct implementation by:
4403 \[
4404 \text{prepare resource state}
4405 \to
4406 \text{entangle and measure}
4407 \to
4408 \text{classical correction}.
4409 \]
4410 The ambient category contains resources not present in the target channel: entanglement, measurement outcomes, and feedforward.  The endpoint can nevertheless be a deterministic unitary.
4411 
4412 This is an archetypal realization defect, but careful accounting is mandatory.  A claimed saving must include resource-state preparation or explicitly treat the state as an external catalyst.
4413 
4414 \subsection{Architecture-constrained gates}
4415 Let $\Gamma=(V,E)$ be a hardware graph.  A restricted two-qubit gate may act only on edges of $E$.  The ambient model may permit a small number of nonlocal interactions, temporary logical relabelings, teleportation edges, or bus-mediated gates.
4416 
4417 For a target $U$, define
4418 \[
4419 \ell_\Gamma(U)
4420 =
4421 \text{minimum hardware-respecting cost},
4422 \]
4423 and compare it with an enlarged graph $\Gamma'$.  A matched routing excursion has the form
4424 \[
4425 \pi
4426 \;W\;
4427 \pi^{-1},
4428 \]
4429 where $\pi$ is a logical permutation.  The excursion is profitable when many gates in $W$ become local in the permuted frame.
4430 
4431 \begin{figure}[ht]
4432 \centering
4433 \includegraphics[width=.91\textwidth]{assets/g_resource_pareto.pdf}
4434 \caption{Gate-set defects generally live in a multi-resource Pareto geometry.}
4435 \label{g:fig:resource-pareto}
4436 \end{figure}
4437 
4438 \subsection{Depth, count, and space-time volume}
4439 Let $g_t$ be the set of gates scheduled in layer $t$.  Common scalar costs are
4440 \[
4441 \sum_t |g_t|,
4442 \qquad
4443 \#\{t:g_t\ne\varnothing\},
4444 \qquad
4445 \sum_t \#\{\text{active qubits in layer }t\}.
4446 \]
4447 A catalyst may reduce count but increase depth, or vice versa.  Space-time volume is often the more stable hardware quantity.
4448 
4449 For stochastic error rates $p_g$, a first-order weighted cost is
4450 \[
4451 C_{\mathrm{err}}(W)=\sum_{g\in W}-\log(1-p_g).
4452 \]
4453 This additive approximation can be inserted directly into Dijkstra search.  It does not capture coherent or correlated errors, but it produces a declared and reproducible metric.
4454 
4455 \subsection{Approximate synthesis}
4456 For continuous gate sets, define
4457 \[
4458 \ell_{\mathrm{res},\varepsilon}(U)
4459 =
4460 \min\{\cost(W):\|W-U\|\le\varepsilon\}.
4461 \]
4462 There are two distinct border phenomena:
4463 \begin{enumerate}
4464 \item algebraic border length, where a target lies in the closure of a bounded exact word locus;
4465 \item analytic approximation length, where an error tolerance is explicitly permitted.
4466 \end{enumerate}
4467 They should not be conflated.
4468 
4469 A catalyst can improve the asymptotic Solovay--Kitaev or number-theoretic approximation constant even when exact synthesis is impossible in both models.
4470 
4471 \subsection{Resource theories and monotones}
4472 A quantum resource theory provides free states, free operations, and monotones.  Gate-set distortion adds a path-sensitive question: the endpoint may be free even though the path temporarily creates resource.
4473 
4474 A state monotone $M(\rho)$ alone may fail because the catalyst acts at the channel level.  Useful channel-level quantities include:
4475 \begin{itemize}
4476 \item robustness or magic capacity,
4477 \item entangling power,
4478 \item operator Schmidt rank,
4479 \item Choi-state resource measures,
4480 \item symmetry asymmetry of the channel,
4481 \item amortized resource generation.
4482 \end{itemize}
4483 A lower bound must relate the cumulative or peak resource to the declared gate cost and account for cancellation.
4484 
4485 \subsection{A categorical amplification principle}
4486 Suppose a monoidal category admits a tensor product and a cost satisfying
4487 \[
4488 c_{\mathrm{amb}}(f\otimes g)
4489 \le
4490 c_{\mathrm{amb}}(f)+c_{\mathrm{amb}}(g).
4491 \]
4492 If restricted cost is additive on a target family, then any one-copy defect amplifies linearly under independent tensor powers.  Superlinear amplification requires a normalization in which dimensions multiply, as in the matrix tensor rule of the core theory, or a joint-synthesis synergy across copies.
4493 
4494 \subsection{Experimental standards}
4495 Every architecture, measurement, or ancilla claim should state:
4496 \begin{enumerate}
4497 \item gate alphabet and native connectivity;
4498 \item clean, dirty, catalytic, or consumable ancilla convention;
4499 \item deterministic or postselected implementation;
4500 \item exact or approximate endpoint condition;
4501 \item total, weighted, depth, or Pareto cost;
4502 \item whether resource-state preparation is included;
4503 \item whether qubit relabeling is free;
4504 \item certificate of restoration on all inputs.
4505 \end{enumerate}
4506 Without these declarations, two reported ``gate counts'' may refer to incomparable problems.
4507 
4508 \begin{conjecturebox}
4509 For several common symmetry and architecture restrictions, a constant-size restored excursion should yield an unbounded saving on structured target families.  The unitriangular construction proves this phenomenon for directed linear information flow; analogous theorems for charge sectors, measurement branches, and nonlocal routing remain open.
4510 \end{conjecturebox}
4511 
4512 \chapter{Packets, types, holonomy, and restricted realization}
4513 \section{Packets, types, holonomy, and restricted realization}\label{g:ch:packets}
4514 \index{spherical packet}
4515 \index{type packet}
4516 \index{holonomy packet}
4517 \index{realization fiber}
4518 \index{quantum Latin square}
4519 \index{Langlands-style packet}
4520 
4521 
4522 \subsection{Why coarse spectra are not enough}
4523 A finite symmetry problem often comes with a natural commuting operator algebra.  Its joint spectrum is attractive because it is canonical, compact, and computationally cheap.  Yet the joint eigenvalues and their multiplicities can be identical across objects whose realization behavior is different.
4524 
4525 This chapter develops the hierarchy
4526 \begin{equation}\label{g:eq:packet-hierarchy}
4527 \text{spherical packet}
4528 \prec
4529 \text{embedded type packet}
4530 \prec
4531 \text{holonomy packet}
4532 \prec
4533 \text{realization fiber}.
4534 \end{equation}
4535 The relation $\prec$ means ``retains strictly more potentially relevant information,'' not that every refinement is complete.
4536 
4537 \begin{figure}[ht]
4538 \centering
4539 \includegraphics[width=.95\textwidth]{assets/g_packet_hierarchy.pdf}
4540 \caption{The packet hierarchy used to organize finite threshold systems.}
4541 \label{g:fig:packet-realization-hierarchy}
4542 \end{figure}
4543 
4544 \subsection{Spherical packets}
4545 Let $T_1,\ldots,T_m$ be commuting normal operators on a finite-dimensional Hilbert space.  Their unique coarsest joint spectral resolution is
4546 \[
4547 T_j=\sum_{\lambda}t_j(\lambda)B_\lambda,
4548 \qquad
4549 \sum_\lambda B_\lambda=I.
4550 \]
4551 The tuple
4552 \[
4553 \lambda=(t_1(\lambda),\ldots,t_m(\lambda))
4554 \]
4555 is the spherical label.  The abstract spectral packet records these labels and the ranks of $B_\lambda$.
4556 
4557 Two different embedded systems can have the same abstract packet.  The actual matrices $B_\lambda$, endpoint coefficients, and transition operators may still differ.
4558 
4559 \begin{principle}[Spherical collapse]
4560 Passing from embedded operators to eigenvalues and multiplicities can erase exactly the incidence or transition data that controls restricted realization.
4561 \end{principle}
4562 
4563 \subsection{The Latin-square association algebra}
4564 A Latin square $L$ of order $n$ has $n^2$ cells.  Let $R,C,S$ be adjacency matrices for equality of row, column, and symbol.  The algebra generated by $I,J,R,C,S$ is commutative and its abstract multiplication table depends only on $n$, not on the paratopy class of $L$.
4565 
4566 Define
4567 \[
4568 Q_R=\frac{I+R}{n},
4569 \qquad
4570 Q_C=\frac{I+C}{n},
4571 \qquad
4572 Q_S=\frac{I+S}{n},
4573 \qquad
4574 B_0=\frac{J}{n^2}.
4575 \]
4576 Then the five joint projectors are
4577 \[
4578 B_0,
4579 \quad Q_R-B_0,
4580 \quad Q_C-B_0,
4581 \quad Q_S-B_0,
4582 \quad I-Q_R-Q_C-Q_S+2B_0.
4583 \]
4584 Their multiplicities are
4585 \[
4586 1,
4587 \quad n-1,
4588 \quad n-1,
4589 \quad n-1,
4590 \quad (n-1)(n-2).
4591 \]
4592 The Latin-square graph $R+C+S$ has universal spectrum
4593 \[
4594 3(n-1)^1,
4595 \qquad
4596 (n-3)^{3(n-1)},
4597 \qquad
4598 (-3)^{(n-1)(n-2)}.
4599 \]
4600 At $n=6$ this becomes
4601 \[
4602 15^1,\qquad3^{15},\qquad(-3)^{20}.
4603 \]
4604 Thus the graph spectrum cannot distinguish the twelve main classes of order six.
4605 
4606 \begin{provedbox}
4607 The displayed projector formulas depend only on the Latin-square axioms and the order.  They therefore prove that the abstract $R,C,S$ joint eigenvalue packets cannot distinguish squares of the same order.  This conclusion does not require an enumeration of the order-six main classes.
4608 \end{provedbox}
4609 
4610 \subsection{Transition fusion also collapses}
4611 Let $\rho_i$ be the row permutations of a Latin square.  The symmetrized aggregate of all pair transitions satisfies
4612 \begin{equation}\label{g:eq:transition-fusion}
4613 \sum_{i<j}
4614 \left(
4615 P_{\rho_i\rho_j^{-1}}
4616 +
4617 P_{\rho_j\rho_i^{-1}}
4618 \right)
4619 =n(J-I).
4620 \end{equation}
4621 Hence first-order fusion destroys the class information as well.
4622 
4623 The lesson is general: summing typed transitions can be as destructive as discarding the embedded projectors.  Order and labels matter.
4624 
4625 \subsection{Embedded type data}
4626 A type packet retains the actual projectors, support partitions, distinguished incidence sets, or local representation types.  Examples include:
4627 \begin{itemize}
4628 \item the row, column, and symbol partitions of a Latin square;
4629 \item a projective-line closure system;
4630 \item the flag stabilized by a circuit subgroup;
4631 \item support patterns of unitary or quantum-Latin entries;
4632 \item ramification or block data in a finite group action.
4633 \end{itemize}
4634 
4635 A projective-line closure procedure can supply additional type operators, such as adjacency operators of a line spread.  Whether a particular added operator separates two classes is a further question.  The present archive does not include the separate order-six projective computation, so it supplies no new finite certification of that comparison.
4636 
4637 \subsection{Holonomy packets}
4638 Let a family of local charts or rows be represented by permutations $\rho_i$.  Define normalized transitions
4639 \[
4640 h_{ij}=\rho_i\rho_j^{-1}
4641 \]
4642 and the transition group
4643 \[
4644 H_r(L)=\langle h_{ij}:i,j\rangle.
4645 \]
4646 A holonomy packet may include:
4647 \begin{itemize}
4648 \item the isomorphism type or order of $H_r(L)$,
4649 \item the cycle-type inventory of the distinguished $h_{ij}$,
4650 \item block systems and orbit partitions,
4651 \item characters or matrix coefficients of words in the $h_{ij}$,
4652 \item noncommutative moments
4653 \[
4654 \operatorname{tr}(h_{i_1j_1}\cdots h_{i_kj_k}),
4655 \]
4656 \item the corresponding packets for row, column, and symbol roles.
4657 \end{itemize}
4658 
4659 Isotopy conjugates these transition groups; paratopy permutes the three roles.  Therefore the unordered multiset of role signatures is a paratopy invariant.
4660 
4661 \begin{skeletonbox}
4662 For a specified collection of Latin squares, one can compute transition-group orders, pair-transition cycle inventories, and nontrivial block sizes, then test whether the resulting role signatures separate the collection.  The separate order-six input tables and verifier are not included in this archive, so pairwise separation of all twelve main classes is an open verification obligation here.
4663 \end{skeletonbox}
4664 Even a complete discrete classification would not prove orthonormal representability.  Noncommutative transition data are candidate refinements of the information lost under spherical fusion.
4665 
4666 \subsection{Imprimitivity as hidden decomposition}
4667 A transitive permutation group is imprimitive when it preserves a nontrivial block system.  In combinatorial designs, imprimitivity often signals a subsquare, product, congruence, or module decomposition.
4668 
4669 For a Latin square of order $2m$, normalize one row to the identity permutation on the symbols.  An $m\times m$ Latin subsquare determines a partition of the symbols into its $m$ symbols and their complement.  Rows meeting the subsquare preserve the two corresponding column blocks, and the remaining rows exchange them.  Thus normalized row transitions preserve this two-block system.  Conversely, if all normalized row transitions preserve a partition into two blocks of size $m$, exactly $m$ rows send a fixed column block into a fixed symbol block, producing an $m\times m$ Latin subsquare.  This is a structural criterion.  Counting the order-six classes with this property requires separate input representatives.
4670 
4671 \begin{principle}[Clifford-type decomposition]
4672 Combinatorial substructure can be detected as imprimitivity of a transition packet.  The spherical packet sees aggregate multiplicities; the holonomy packet sees how those multiplicities are assembled into blocks.
4673 \end{principle}
4674 
4675 \subsection{Realization fibers}
4676 Let $P$ denote packet data and let
4677 \[
4678 \operatorname{Real}_{\mathrm{res}}(P)
4679 \]
4680 be the space of restricted realizations compatible with $P$.  The packet may completely classify the discrete object while the realization fiber remains empty, positive dimensional, disconnected, or singular.
4681 
4682 Examples of realization conditions include:
4683 \begin{itemize}
4684 \item a flag-preserving geodesic with a declared length;
4685 \item a product-state orthonormal representation;
4686 \item a positive semidefinite Gram matrix with a zero pattern;
4687 \item a tensor factorization;
4688 \item a global descent object compatible with local packets;
4689 \item a circuit satisfying ancilla restoration on every input.
4690 \end{itemize}
4691 
4692 Thus classification and realization are distinct layers.
4693 
4694 \subsection{Quantum Latin squares as an existence defect}
4695 A quantum Latin square is an array \cite{s:MustoVicary2016} of vectors whose rows and columns are orthonormal bases.  Ball and Simoens prove that a pair of non-entangled mutually orthogonal quantum Latin squares of order six does not exist, while earlier work provides entangled order-six solutions and hence AME$(4,6)$ states \cite{s:BallSimoens2026,s:RatherEtAl2022,g:RatherEtAl2023}.
4696 
4697 This is naturally expressed as
4698 \[
4699 \operatorname{Real}_{\mathrm{product}}(P_6)=\varnothing,
4700 \qquad
4701 \operatorname{Real}_{\mathrm{entangled}}(P_6)\ne\varnothing.
4702 \]
4703 It is an existence defect, not a gate-count defect.
4704 
4705 \begin{figure}[ht]
4706 \centering
4707 \includegraphics[width=.92\textwidth]{assets/g_quantum_latin_realization_gap.pdf}
4708 \caption{The order-six quantum-Latin distinction is a restricted-versus-ambient realization gap.}
4709 \label{g:fig:quantum-latin-gap}
4710 \end{figure}
4711 
4712 The source proof uses support patterns, a reduction to one classical square, orthonormal representations of complements of Latin-square graphs, projective-line closure, finite case analysis over twelve main classes, and a continuous argument for the two remaining subsquare cases.  No theorem in the unitriangular or Clifford chapters is inferred from this result.
4713 
4714 \subsection{First-arrival packets}
4715 For a finite generator set $S$, the endpoint Green kernel
4716 \[
4717 \mathcal G_{S,g}(z)
4718 =
4719 \langle\delta_g,(I-zA_S)^{-1}\delta_e\rangle
4720 \]
4721 contains more information than the spectrum of $A_S$.  Its first nonzero degree is the distance to $g$.
4722 
4723 If
4724 \[
4725 A_S=\sum_\lambda \lambda B_\lambda,
4726 \]
4727 then
4728 \[
4729 \mathcal G_{S,g}(z)
4730 =
4731 \sum_\lambda
4732 \frac{\langle\delta_g,B_\lambda\delta_e\rangle}{1-\lambda z}.
4733 \]
4734 The endpoint matrix coefficients of the embedded projectors determine cancellation between spectral components.  This is the metric analogue of retaining a type rather than only an unramified eigencharacter.
4735 
4736 \subsection{Typed Green kernels}
4737 Let $H\le G$ and let $\mu_k(h)$ count ambient words of length $k$ with holonomy $h\in H$.  For an irreducible representation $\tau$ of $H$, define
4738 \[
4739 \widehat\mu_k(\tau)
4740 =
4741 \sum_{h\in H}\mu_k(h)\tau(h)
4742 \]
4743 and
4744 \[
4745 \widehat{\mathcal G}_\tau(z)
4746 =
4747 \sum_{k\ge0}\widehat\mu_k(\tau)z^k.
4748 \]
4749 Fourier inversion recovers every $\mu_k(h)$.  The trivial representation records only total return to the subgroup; nontrivial types resolve the holonomy.
4750 
4751 \begin{provedbox}
4752 For finite $H$, the full family of typed Green kernels over $\widehat H$ determines every endpoint Green series and therefore every ambient word distance from the identity to an element of $H$.
4753 \end{provedbox}
4754 
4755 \subsection{Operational Langlands analogy}
4756 The hierarchy resembles the local organization of representation theory:
4757 \[
4758 \text{spherical character}
4759 \to
4760 \text{type}
4761 \to
4762 \text{ramification or monodromy}
4763 \to
4764 \text{realization and descent}.
4765 \]
4766 The analogy is useful because it prevents coarse spectral data from being mistaken for a complete correspondence.  It does not imply that global Langlands reciprocity predicts either the circuit threshold or the quantum-Latin result.
4767 
4768 \begin{boundarybox}
4769 The word ``Langlands'' in this monograph refers to an operational packet architecture: commuting local spectra, type refinement, noncommutative holonomy, tensor assembly, and descent obligations.  No general automorphic or Galois correspondence is claimed or used.
4770 \end{boundarybox}
4771 
4772 \subsection{A general finite threshold system}
4773 A packet-resolved threshold system consists of:
4774 \begin{enumerate}
4775 \item a finite group, groupoid, or association scheme;
4776 \item a commutative spherical algebra with exact projectors;
4777 \item embedded incidence or type data;
4778 \item a transition group or monodromy representation;
4779 \item restricted and ambient realization categories;
4780 \item a metric, multiplicity, or descent obstruction.
4781 \end{enumerate}
4782 
4783 The first threshold may then be defined as
4784 \[
4785 \tau=
4786 \min\{n:\exists P\text{ with }c_{\mathrm{res}}(P)>c_{\mathrm{amb}}(P)\}.
4787 \]
4788 The cost can be finite or infinite.
4789 
4790 \subsection{Open problems}
4791 \begin{question}
4792 For which finite association schemes does the full embedded Bose--Mesner algebra determine the restricted realization fiber?
4793 \end{question}
4794 \begin{question}
4795 What bounded degree of noncommutative transition moments separates all Latin squares of a fixed order?
4796 \end{question}
4797 \begin{question}
4798 Can typed Green kernels yield new lower bounds without enumerating the full ambient group?
4799 \end{question}
4800 \begin{question}
4801 When does imprimitivity of a transition packet characterize a tensor or subsquare decomposition in quantum combinatorial designs?
4802 \end{question}
4803 
4804 \chapter{The computational atlas and open directions}
4805 \section{The exact computational atlas}\label{g:ch:atlas}
4806 \index{breadth-first search}
4807 \index{zero-one BFS}
4808 \index{Dijkstra algorithm}
4809 \index{certificate}
4810 \index{reproducibility}
4811 
4812 
4813 \subsection{Purpose and design}
4814 The accompanying code is an audit-oriented finite mathematics package rather than a production compiler.  Its goals are:
4815 \begin{enumerate}
4816 \item exact state representations with no floating-point ambiguity;
4817 \item complete finite search where the state space is tractable;
4818 \item explicit witnesses and reconstructible paths;
4819 \item small, dependency-free core algorithms;
4820 \item frozen JSON results and regression tests;
4821 \item separation between proved, computed, and proposed claims.
4822 \end{enumerate}
4823 
4824 The package is named \texttt{catalytic\_gate\_atlas}.  Binary matrices are tuples of integer row bitmasks, and reversible Boolean maps are exact permutations of basis-state indices.
4825 
4826 \begin{figure}[ht]
4827 \centering
4828 \includegraphics[width=.96\textwidth]{assets/g_computational_pipeline.pdf}
4829 \caption{The finite certificate pipeline used throughout the computational atlas.}
4830 \label{g:fig:computational-pipeline}
4831 \end{figure}
4832 
4833 \subsection{State models}
4834 \subsubsection{Binary matrices}
4835 An $m\times m$ matrix over $\F_2$ is stored as
4836 \[
4837 (r_0,\ldots,r_{m-1}),
4838 \]
4839 where bit $j$ of $r_i$ is the $(i,j)$ entry.  Matrix multiplication is exact XOR accumulation.
4840 
4841 \subsubsection{Symplectic Clifford states}
4842 An $n$-qubit Clifford modulo global phase and Pauli translation is represented by its action on Pauli exponent vectors
4843 \[
4844 (x\mid z)\in\F_2^{2n}.
4845 \]
4846 The state space is $\Sp(2n,2)$.  The restricted parabolic group is generated by $S$, CZ, and CNOT; the ambient group additionally permits $H$.
4847 
4848 \subsubsection{Classical reversible states}
4849 A reversible map on $n$ bits is stored as a permutation of $\{0,\ldots,2^n-1\}$.  Composition is exact.  The affine subgroup is generated by $X$ and CNOT, and the ambient three-bit group adds Toffoli.
4850 
4851 \subsection{Shortest-path engines}
4852 The package implements:
4853 \begin{itemize}
4854 \item breadth-first search for unit costs;
4855 \item $0$--$1$ breadth-first search when gates are free or unit cost;
4856 \item Dijkstra search for general nonnegative integer weights;
4857 \item parent maps for witness reconstruction;
4858 \item defect distributions on a restricted target set.
4859 \end{itemize}
4860 
4861 \begin{algorithm}[Breadth-first defect census]
4862 Given restricted generators $S_R$, ambient generators $S_A$, and identity $e$:
4863 \begin{enumerate}
4864 \item compute $d_R$ on $\langle S_R\rangle$;
4865 \item compute $d_A$ on $\langle S_A\rangle$;
4866 \item for every restricted state $x$, compare $d_R(x)$ and $d_A(x)$;
4867 \item record the pair $(d_R(x),d_A(x))$ and reconstruct witnesses for strict inequalities.
4868 \end{enumerate}
4869 \end{algorithm}
4870 
4871 For a finite group this is complete because every vertex reachable from the identity is visited exactly once at its minimum distance.
4872 
4873 \subsection{Zero-cost gates}
4874 When local Clifford gates are free and entangling gates cost one, ordinary BFS is invalid.  The package uses a deque-based $0$--$1$ BFS.  A zero-cost edge is pushed to the front and a unit-cost edge to the back.  The resulting labels are exact shortest entangling costs.
4875 
4876 A common error is to quotient by free gates without proving that the quotient preserves the target subset and all left/right actions.  The atlas avoids this issue by running $0$--$1$ BFS directly on the finite group for the reported small cases.
4877 
4878 \subsection{The optimized Clifford verifier}
4879 The three-qubit symplectic group has
4880 \[
4881 |\Sp(6,2)|=1{,}451{,}520
4882 \]
4883 states.  A compact C++ implementation enumerates the full group and the parabolic subgroup exactly.  It supports:
4884 \begin{itemize}
4885 \item total primitive count;
4886 \item total count with unit-cost SWAP;
4887 \item entangling count with $H$ and $S$ free;
4888 \item exact distance distributions and JSON output.
4889 \end{itemize}
4890 The C++ program and the independent Python implementation use the same gate matrices but different traversal code.  Witness reconstruction is supplied by the Python implementation, not by the C++ census executable.
4891 
4892 \subsection{Computed Clifford census}
4893 \begin{longtable}{@{}ccccccc@{}}
4894 \toprule
4895 $n$ & Metric & SWAP & $|P_n|$ & $|\Sp(2n,2)|$ & Defects & Max defect\\
4896 \midrule
4897 1 & total & no & 2 & 6 & 0 & 0\\
4898 1 & entangling & no & 2 & 6 & 0 & 0\\
4899 2 & total & no & 48 & 720 & 0 & 0\\
4900 2 & entangling & no & 48 & 720 & 4 & 1\\
4901 3 & total & no & 10,752 & 1,451,520 & 24 & 1\\
4902 3 & total & yes & 10,752 & 1,451,520 & 0 & 0\\
4903 3 & entangling & no & 10,752 & 1,451,520 & 1,624 & 2\\
4904 \bottomrule
4905 \end{longtable}
4906 
4907 The detailed defect distributions are:
4908 \[
4909 \begin{array}{c|l}
4910 \text{model}&\text{restricted}\to\text{ambient pairs}\\
4911 \hline
4912 n=2\text{ entangling}&3\to2:4\\
4913 n=3\text{ total}&7\to6:6,\quad8\to7:18\\
4914 n=3\text{ entangling}&3\to2:24,\ 4\to3:432,\ 5\to4:1056,\ 6\to4:48,\ 6\to5:64.
4915 \end{array}
4916 \]
4917 
4918 \begin{computedbox}
4919 Every entry in the table is a complete finite enumeration in the declared binary symplectic model.  Phases and Pauli translations are not part of the state space.  These are exact results for that quotient model, not full hardware Clifford optimizations.
4920 \end{computedbox}
4921 
4922 \subsection{Computed affine-versus-Toffoli census}
4923 For three bits:
4924 \[
4925 |\operatorname{AGL}(3,2)|=1344,
4926 \qquad
4927 |S_8|=40320.
4928 \]
4929 The complete census finds no affine target with a strict defect under total primitive count or under entangling count with NOT free.
4930 
4931 \begin{longtable}{@{}ccccc@{}}
4932 \toprule
4933 Metric & Restricted size & Ambient size & Restricted diameter & Defects\\
4934 \midrule
4935 Total & 1,344 & 40,320 & 7 & 0\\
4936 Entangling & 1,344 & 40,320 & 6 & 0\\
4937 \bottomrule
4938 \end{longtable}
4939 
4940 \subsection{Linear symbolic checks}
4941 The Python module verifies that the displayed six-row ambient and restricted words produce the same canonical target modulo
4942 \[
4943 2,3,5,8.
4944 \]
4945 The lower bounds and ring universality are proved in the core chapter; these modular checks are regression tests rather than the logical basis of the theorem.
4946 
4947 \subsection{Witness format}
4948 A witness record contains:
4949 \begin{itemize}
4950 \item the target matrix or permutation;
4951 \item restricted and ambient costs;
4952 \item a named restricted gate path;
4953 \item a named ambient gate path;
4954 \item the metric and gate alphabet;
4955 \item the state-model convention.
4956 \end{itemize}
4957 For example, the two-qubit entangling Clifford witness has restricted path
4958 \[
4959 \CX_{0\to1},\ S_1,\ \CX_{1\to0},\ \CX_{0\to1}
4960 \]
4961 and ambient path
4962 \[
4963 H_1,\ \CX_{1\to0},\ \CX_{0\to1},\ H_0,\ S_1,\ S_0.
4964 \]
4965 Only two gates in the ambient path are charged by the entangling metric.
4966 
4967 \subsection{Certificates beyond full enumeration}
4968 For larger systems, the following certificate styles are supported in principle.
4969 \begin{enumerate}
4970 \item \textbf{Meet in the middle.}  Store forward and backward balls whose radii sum to the candidate length.
4971 \item \textbf{SAT/SMT.}  Encode gate choices and endpoint equations; use an UNSAT certificate below the claimed optimum.
4972 \item \textbf{Integer programming.}  Useful when a fixed gate skeleton leaves discrete routing choices.
4973 \item \textbf{Algebraic elimination.}  Eliminate continuous gate parameters from bounded-length word equations.
4974 \item \textbf{Dual potentials.}  Exhibit a one-Lipschitz potential attaining the claimed lower bound.
4975 \item \textbf{Quotient search.}  Search cosets only after proving that the quotient is compatible with the cost and target class.
4976 \end{enumerate}
4977 
4978 \subsection{Multiobjective search}
4979 Let each gate have a vector cost in $\N^r$.  At each state, retain only nondominated labels.  The algorithm terminates for finite state spaces with a bounded search region, but the frontier can grow exponentially.
4980 
4981 A practical exact strategy is to scalarize with several positive weight vectors, use the resulting optima to identify candidate Pareto points, and then certify each candidate by constrained search.
4982 
4983 \subsection{Reproducibility commands}
4984 From the \texttt{code} directory:
4985 \begin{lstlisting}[style=pythonstyle,caption={Python atlas commands.}]
4986 python -m pip install -e . --no-build-isolation
4987 python scripts/run_atlas.py --output ../results/atlas_small.json
4988 python -m pytest tests
4989 \end{lstlisting}
4990 The optimized three-qubit verifier can be compiled by
4991 \begin{lstlisting}[style=cppstyle,caption={C++ Clifford verifier.}]
4992 g++ -O3 -std=c++20 scripts/clifford_census.cpp -o scripts/clifford_census
4993 ./scripts/clifford_census --n 3 --metric total --output ../results/clifford_n3_total.json
4994 ./scripts/clifford_census --n 3 --metric entangling --output ../results/clifford_n3_entangling.json
4995 \end{lstlisting}
4996 
4997 \subsection{Validation policy}
4998 The release uses four layers of validation.
4999 \begin{enumerate}
5000 \item Unit tests for matrix, permutation, and path primitives.
5001 \item Cross-checks of group sizes against known finite formulas.
5002 \item Independent Python and C++ computations for selected Clifford cases.
5003 \item Frozen JSON outputs and SHA-256 manifests in the release archive.
5004 \end{enumerate}
5005 
5006 \subsection{Scaling limits}
5007 Full group enumeration grows rapidly:
5008 \[
5009 |\Sp(2n,2)|
5010 =2^{n^2}\prod_{j=1}^n(4^j-1).
5011 \]
5012 The four-qubit symplectic group is far beyond direct Python BFS.  Future work should exploit:
5013 \begin{itemize}
5014 \item double-coset normal forms,
5015 \item Bruhat or parabolic decompositions,
5016 \item admissible heuristics for A* search,
5017 \item SAT encodings,
5018 \item orbit reduction,
5019 \item tensor-network representations,
5020 \item distributed meet in the middle.
5021 \end{itemize}
5022 
5023 \subsection{What the atlas does not prove}
5024 A finite census establishes only the declared finite model.  It does not prove:
5025 \begin{itemize}
5026 \item an asymptotic theorem without a separate proof,
5027 \item a hardware advantage under a different cost,
5028 \item robustness to approximation,
5029 \item equivalence after adding ancillas,
5030 \item a result for global phases or Pauli translations if they were quotiented out.
5031 \end{itemize}
5032 The status metadata in every result file is intended to make these boundaries machine readable.
5033 
5034 \section{Reusable theorem templates}\label{g:ch:templates}
5035 \index{theorem template}
5036 \index{lower bound}
5037 \index{dimension per gate}
5038 \index{tensor amplification}
5039 
5040 
5041 \subsection{Purpose}
5042 This chapter collects proof architectures that recur across gate logics.  Each template separates the easy upper-bound identity from the difficult lower-bound obligation.  The templates are not claims that every gate hierarchy satisfies the hypotheses.
5043 
5044 \subsection{Template I: catalytic conjugation}
5045 Let $H\le G$ have restricted and ambient costs with $\ellAmb(g^{-1})=\ellAmb(g)$.  Choose $g\in G$ and $h_1,\ldots,h_m\in H$ such that
5046 \[
5047 U=g h_m\cdots h_1 g^{-1}\in H.
5048 \]
5049 Then
5050 \[
5051 \ellAmb(U)
5052 \le
5053 2\ellAmb(g)+\sum_i\ellAmb(h_i).
5054 \]
5055 
5056 \begin{theorem}[Catalytic comparison template]
5057 Assume a restricted lower bound of the form
5058 \[
5059 \ellRes(U)
5060 \ge
5061 \sum_i r_i-\beta,
5062 \]
5063 where $r_i$ is the restricted cost of the $i$th transported obligation and $\beta$ is the maximum certified sharing.  Then
5064 \[
5065 \Delta(U)
5066 \ge
5067 \sum_i r_i-\beta
5068 -
5069 2\ellAmb(g)-\sum_i\ellAmb(h_i).
5070 \]
5071 \end{theorem}
5072 
5073 The proof is immediate.  The research content lies in bounding $\beta$.
5074 
5075 \subsection{Template II: amortized consumers}
5076 Suppose a catalyst costs $c_{\mathrm{open}}+c_{\mathrm{close}}$ and each of $m$ consumers saves at least $s_i$ restricted cost.  Then
5077 \[
5078 \Delta(U)
5079 \ge
5080 \sum_{i=1}^m s_i
5081 -c_{\mathrm{open}}-c_{\mathrm{close}}-r,
5082 \]
5083 where $r$ is repair or interference cost.  A threshold occurs when the right side first becomes positive.
5084 
5085 This template explains the three-cross rule in the linear atom and guides searches in phase, Gaussian, and routing models.
5086 
5087 \subsection{Template III: first-arrival Green valuation}
5088 Let $S$ be a finite symmetric generating set and
5089 \[
5090 A_S=\sum_{s\in S}\rho(s).
5091 \]
5092 Then
5093 \[
5094 \mathcal G_{S,g}(z)
5095 =\sum_{k\ge0}\langle\delta_g,A_S^k\delta_e\rangle z^k.
5096 \]
5097 
5098 \begin{theorem}[First-arrival template]
5099 If word multiplicities are nonnegative, then
5100 \[
5101 d_S(e,g)=\ord_{z=0}\mathcal G_{S,g}(z).
5102 \]
5103 For restricted and ambient sets,
5104 \[
5105 \Delta(g)=\ord_0\mathcal G_{S_R,g}-\ord_0\mathcal G_{S_A,g}.
5106 \]
5107 \end{theorem}
5108 
5109 This template provides an exact spectral restatement.  To turn it into a lower bound without enumeration, one needs control of the endpoint projector coefficients.
5110 
5111 \subsection{Template IV: one-Lipschitz potentials}
5112 Let $F$ be a function on circuit states satisfying
5113 \[
5114 F(I)=0,
5115 \qquad
5116 |F(gs)-F(g)|\le c(s)
5117 \]
5118 for every allowed restricted gate $s$.  Then
5119 \[
5120 \ellRes(U)\ge F(U).
5121 \]
5122 
5123 Potential design steps:
5124 \begin{enumerate}
5125 \item choose a decomposition into cuts, packets, or degree layers;
5126 \item prove a gate changes the total charge by at most its cost;
5127 \item ensure cancellations cannot create free progress on many layers;
5128 \item evaluate the target exactly.
5129 \end{enumerate}
5130 Static sums of ranks are often too coarse in ambient models; time-expanded or target-relative potentials may be required.
5131 
5132 \subsection{Template V: dimension per gate}
5133 Let $X$ be an algebraic family of elementary gates whose irreducible components have dimension at most $r$.  Let $V$ be an irreducible target variety of dimension $N$.
5134 
5135 \begin{theorem}[Dimension-per-gate template]
5136 The closure of the locus reachable in $L$ gates has dimension at most $rL$.  If $rL<N$, a generic point of $V$ is not reachable in $L$ gates.
5137 \end{theorem}
5138 
5139 If every target in $V$ has a restricted construction of length at most $N/r$, then generic restricted and ambient lengths coincide at that value, provided the same parameter bound applies to the ambient alphabet.
5140 
5141 \subsection{Template VI: defect codimension}
5142 Assume every target has restricted cost at most $M$.  A defect of size at least $d$ implies ambient cost at most $M-d$.  If the $(M-d)$-gate ambient locus has dimension at most $N-d$, then
5143 \[
5144 \codim\overline{\mathcal D_{\ge d}}\ge d.
5145 \]
5146 This is the general mechanism behind algebraic rarity.
5147 
5148 \subsection{Template VII: finite-field sparsity}
5149 Suppose there are at most $B$ gate directions and at most $q^r$ parameter choices per gate over $\F_q$.  Then the number of words of length at most $L$ is at most
5150 \[
5151 \sum_{j=0}^L(Bq^r)^j.
5152 \]
5153 If the target family has $q^N$ points and defect $d$ forces $L\le (N-d)/r$, this yields a density bound of order $q^{-d}$ up to a fixed combinatorial factor.
5154 
5155 The estimate counts words, not distinct endpoints, and is therefore an upper bound without injectivity assumptions.
5156 
5157 \subsection{Template VIII: block retraction}
5158 Let a large restricted group contain a smaller one through a homomorphic embedding $\iota$, and suppose a homomorphic retraction $\pi$ satisfies $\pi\iota=\operatorname{id}$.  Require that every large restricted generator maps to a small restricted word of no greater cost.  Then
5159 \[
5160 \ell_{\mathrm{large,res}}(\iota U)
5161 \ge
5162 \ell_{\mathrm{small,res}}(U).
5163 \]
5164 If the ambient embedding preserves gate cost,
5165 \[
5166 \Delta_{\mathrm{large}}(\iota U)
5167 \ge
5168 \Delta_{\mathrm{small}}(U).
5169 \]
5170 This transfers a catalytic atom to architectures containing it as a retract.
5171 
5172 \subsection{Template IX: exact block coupling}
5173 For block-lower matrices
5174 \[
5175 M=
5176 \begin{pmatrix}
5177 A&0\\
5178 XA&D
5179 \end{pmatrix},
5180 \]
5181 projection to diagonal blocks forces the costs of $A$ and $D$, while rank of the cross block forces at least $\rank X$ cross transmissions.  If $X$ is a partial monomial matrix, the lower bound is attained by direct construction.
5182 
5183 The same logic extends to trees of blocks whenever every coupling layer has an exact rank certificate and the projections are homomorphisms.
5184 
5185 \subsection{Template X: tensor Leibniz rule}
5186 Suppose a restricted complexity is tree tight and satisfies
5187 \[
5188 \ellRes(A\otimes B)
5189 =n\ellRes(A)+m\ellRes(B)
5190 \]
5191 for $A$ of size $m$ and $B$ of size $n$.  If ambient complexity satisfies the corresponding upper bound, then
5192 \[
5193 \Delta(A\otimes B)
5194 \ge
5195 n\Delta(A)+m\Delta(B).
5196 \]
5197 For tensor powers,
5198 \[
5199 \Delta(A^{\otimes r})
5200 \ge
5201 r m^{r-1}\Delta(A).
5202 \]
5203 This is the standard route from a finite atom to an $N\log N$ defect.
5204 
5205 \subsection{Template XI: stable capacity}
5206 If
5207 \[
5208 a_{r+s}\le m^s a_r+m^r a_s,
5209 \]
5210 then
5211 \[
5212 b_r=\frac{a_r}{m^{r-1}}
5213 \]
5214 is subadditive and
5215 \[
5216 \lim_{r\to\infty}\frac{a_r}{r m^{r-1}}
5217 \]
5218 exists by Fekete's lemma.  This defines a regularized ambient cost and exposes possible tensor activation.
5219 
5220 \subsection{Template XII: vector costs}
5221 Let gates carry costs in $\R_+^k$.  A lower bound may be a vector inequality
5222 \[
5223 F(U)\preceq\sum_{g\in W}c(g)
5224 \]
5225 or a family of scalar inequalities indexed by dual weights $w\in\R_+^k$:
5226 \[
5227 w\cdot F(U)\le w\cdot c(W).
5228 \]
5229 A complete Pareto proof may require enough supporting weights to separate the restricted and ambient convex lower hulls.
5230 
5231 \subsection{Template XIII: ancilla restoration}
5232 Let $W$ act on data $D$ and ancilla $A$.  To certify a dirty catalyst, prove the operator identity
5233 \[
5234 W=U_D\otimes I_A
5235 \]
5236 on the full joint space, not only on one ancilla input.  For a clean catalyst, prove
5237 \[
5238 W(\ket\psi\otimes\ket0)
5239 =(U\ket\psi)\otimes\ket0
5240 \]
5241 for all $\ket\psi$.  The distinction changes both the target equations and lower bounds.
5242 
5243 \subsection{Template XIV: symmetry-sector escape}
5244 Given projectors $P_q$, define off-sector transfer blocks
5245 \[
5246 T_{qr}=P_qUP_r.
5247 \]
5248 A restricted gate preserves all diagonal sectors.  An ambient gate changes a controlled collection of blocks.  A candidate potential is a weighted sum of ranks or norms of obligations relative to the final target.  The proof must charge both creation and useful consumption of off-sector coherence.
5249 
5250 \subsection{Template XV: exhaustive threshold classification}
5251 A finite first-threshold theorem should contain:
5252 \begin{enumerate}
5253 \item no defects below size $n_0$;
5254 \item at least one defect at $n_0$;
5255 \item exact classification of every defect at $n_0$ modulo declared equivalence;
5256 \item analytic generation of the exceptional motifs;
5257 \item equality between the analytic set and computational census;
5258 \item witness and completeness certificates.
5259 \end{enumerate}
5260 This is the standard achieved by the six-wire linear core and is the target standard for future gate logics.
5261 
5262 \subsection{A proof-obligation ledger}
5263 Before promoting a catalytic identity to a theorem, record:
5264 \begin{longtable}{@{}p{.29\textwidth}p{.62\textwidth}@{}}
5265 \toprule
5266 Obligation & Required evidence\\
5267 \midrule
5268 Endpoint membership & Symbolic proof that the target lies in the restricted class.\\
5269 Ambient upper bound & Explicit circuit evaluated exactly.\\
5270 Restricted lower bound & Potential, rank, algebraic, search, or certificate argument.\\
5271 Restoration & Identity on all data and work inputs under the chosen convention.\\
5272 Cost compatibility & Same gate alphabet, weights, and free operations in both metrics.\\
5273 Minimal threshold & Exhaustive or symbolic exclusion of smaller instances.\\
5274 Equivalence classification & Orbit or normal-form analysis of all minimal defects.\\
5275 Amplification & Proof that the lower bound and upper construction compose.\\
5276 Reproducibility & Source, frozen outputs, and deterministic commands.\\
5277 \bottomrule
5278 \end{longtable}
5279 
5280 \section{Research program and paper architecture}\label{g:ch:program}
5281 \index{open problem}
5282 \index{research program}
5283 
5284 
5285 \subsection{The central research problem}
5286 For a nested pair of gate models, determine the distortion function
5287 \[
5288 D_n=
5289 \sup_{U\in\mathcal T_n}
5290 \bigl(c_{\mathrm{res}}(U)-c_{\mathrm{amb}}(U)\bigr),
5291 \]
5292 where $\mathcal T_n$ is the target class.  The basic questions are:
5293 \begin{enumerate}
5294 \item Does any defect exist?
5295 \item What is the first size threshold?
5296 \item What is the minimal catalytic motif?
5297 \item Is the effect generic, sparse, or confined to special strata?
5298 \item How does it scale under direct sum, recursion, and tensor products?
5299 \item Which resource vector reveals the first defect?
5300 \item Can the effect survive realistic architecture and fault-tolerant costs?
5301 \end{enumerate}
5302 
5303 \subsection{Established base camp}
5304 The unitriangular theory provides a complete first example:
5305 \begin{itemize}
5306 \item a universal six-row atom over nonzero commutative rings;
5307 \item exact binary and ternary first-threshold evidence;
5308 \item exact classification of twenty binary minimal defects;
5309 \item connected families with two reverse gates and linear saving;
5310 \item microscopic rank-one, bandwidth-one escape;
5311 \item generic rigidity and defect codimension;
5312 \item recursive and tensor amplification to $\Omega(n\log n)$.
5313 \end{itemize}
5314 The small Clifford atlas adds a second gate logic with genuine exact defects and shows that changing the primitive library by adding SWAP can remove them.
5315 
5316 \subsection{Program A: complete the Clifford threshold theory}
5317 The highest-priority quantum project is a paper on parabolic-versus-ambient Clifford synthesis.
5318 
5319 \subsubsection{Immediate tasks}
5320 \begin{enumerate}
5321 \item Extend the analytic four-target free-phase orbit certificate to other cost-preserving Clifford equivalences and larger widths.
5322 \item Classify the twenty-four three-qubit total-count defects under parabolic conjugation and qubit permutations.
5323 \item Derive analytic normal forms for the witness circuits.
5324 \item Prove lower bounds independent of full group enumeration.
5325 \item Test depth, weighted, and architecture-aware metrics.
5326 \item Determine whether a finite defective atom tensor-amplifies.
5327 \end{enumerate}
5328 
5329 \subsubsection{Longer-term questions}
5330 \begin{conjecture}
5331 The parabolic subgroup of $\Sp(2n,2)$ has unbounded additive distortion in the full symplectic group for at least one natural Clifford cost model.
5332 \end{conjecture}
5333 \begin{question}
5334 Does the maximum total-count defect grow as $n$, $n\log n$, or faster?
5335 \end{question}
5336 \begin{question}
5337 Is the disappearance of three-qubit defects after adding unit-cost SWAP a small-width accident or a structural geodesic-convexity phenomenon?
5338 \end{question}
5339 
5340 \subsection{Program B: temporary nonlinearity}
5341 The three-bit affine-versus-Toffoli census is rigid.  The next target is a complete four-bit normal-form search without enumerating $16!$ permutations.
5342 
5343 \subsubsection{Algorithmic plan}
5344 \begin{enumerate}
5345 \item Compute exact affine distances for all $|\operatorname{AGL}(4,2)|=322{,}560$ targets.
5346 \item Enumerate Toffoli sandwiches modulo affine left and right actions.
5347 \item Use ANF equations to retain only affine endpoints.
5348 \item Compare total, Toffoli, CNOT, and fault-tolerant costs.
5349 \item Produce SAT certificates below every claimed optimum.
5350 \end{enumerate}
5351 
5352 \begin{question}
5353 What is the first bit width at which a restored nonlinear excursion shortens an affine target?
5354 \end{question}
5355 \begin{question}
5356 Can temporary degree two yield a family with unbounded saving while the endpoint degree remains one?
5357 \end{question}
5358 
5359 \subsection{Program C: phase-polynomial catalysts}
5360 The phase setting is likely to produce a defect first in a resource other than total primitive count.
5361 
5362 Priority metrics:
5363 \[
5364 T\text{-depth},
5365 \quad
5366 \text{CNOT count at fixed }T\text{-count},
5367 \quad
5368 \text{two-qubit depth},
5369 \quad
5370 \text{architecture-weighted cost}.
5371 \]
5372 A first paper should choose one metric and avoid a diffuse comparison across all resources.
5373 
5374 \begin{question}
5375 Can a restored Hadamard or Clifford frame reduce $T$-depth of a diagonal target without additional ancillas?
5376 \end{question}
5377 \begin{question}
5378 Does tensor activation occur for phase-polynomial $T$-count?
5379 \end{question}
5380 
5381 \subsection{Program D: Gaussian and matchgate systems}
5382 Two concrete first searches are recommended.
5383 \begin{enumerate}
5384 \item Number-conserving versus general fermionic Gaussian synthesis on a small number of modes.
5385 \item Nearest-neighbor versus all-to-all matchgate circuits with weighted fermionic SWAP cost.
5386 \end{enumerate}
5387 Both admit exact orthogonal-matrix representations and have clear architecture relevance.
5388 
5389 \subsection{Program E: symmetry and measurement}
5390 This program should begin with a narrowly declared resource theory, such as:
5391 \begin{itemize}
5392 \item excitation-preserving two-qubit gates versus arbitrary two-qubit gates;
5393 \item unitary Clifford+$T$ versus measurement-assisted Clifford+$T$;
5394 \item clean versus dirty ancillas for a fixed arithmetic family;
5395 \item local architecture versus one reusable nonlocal bus gate.
5396 \end{itemize}
5397 The first objective is not maximal generality but one theorem with exact restoration and cost accounting.
5398 
5399 \subsection{Program F: root-system catalysis}
5400 For a split reductive group with allowed roots $\Psi\subset\Phi$, classify configurations in which a forbidden root acts as a reusable catalyst through Chevalley commutator relations.
5401 
5402 Suggested sequence:
5403 \[
5404 A_2\to B_2=C_2\to G_2\to A_r.
5405 \]
5406 Low-rank nonsimply laced systems are attractive because longer root strings may create more than one useful effect per consumer.
5407 
5408 \begin{question}
5409 Is there a root-system analogue of the three-cross, one-phase threshold?
5410 \end{question}
5411 \begin{question}
5412 Can a $G_2$ root string produce a multiplicative distortion exceeding the clean type-$A$ value $3/2$?
5413 \end{question}
5414 
5415 \subsection{Program G: algebraic defect loci}
5416 For each finite-dimensional gate hierarchy, define bounded word loci and defect strata.  Determine:
5417 \begin{itemize}
5418 \item irreducible components,
5419 \item exact dimension and codimension,
5420 \item singularities and degenerations,
5421 \item border length,
5422 \item finite-field point counts,
5423 \item behavior under tensor products.
5424 \end{itemize}
5425 
5426 \begin{conjecture}
5427 In a broad class of one-parameter elementary gate varieties, defect at least $d$ is generically a codimension-at-least-$d$ condition, with equality on explicit families of components.
5428 \end{conjecture}
5429 
5430 \subsection{Program H: packet-resolved realization}
5431 The packet hierarchy should be developed as a separate mathematical framework rather than appended to every circuit paper.
5432 
5433 Core objectives:
5434 \begin{enumerate}
5435 \item define spherical, type, and holonomy functors for finite transition groupoids;
5436 \item prove information-loss theorems for commutativization;
5437 \item classify when typed Green kernels are sufficient for distance;
5438 \item relate imprimitivity to combinatorial decomposition;
5439 \item formalize realization fibers and descent obstructions.
5440 \end{enumerate}
5441 
5442 \subsection{Recommended paper sequence}
5443 \begin{longtable}{@{}>{\raggedright\arraybackslash}p{.08\textwidth}>{\raggedright\arraybackslash}p{.37\textwidth}>{\raggedright\arraybackslash}p{.45\textwidth}@{}}
5444 \toprule
5445 Paper & Working title & Core result\\
5446 \midrule
5447 I & Catalytic escape from unitriangularity & Completed linear threshold, rarity, and asymptotic distortion.\\
5448 II & Catalytic basis escape in Clifford synthesis & Exact parabolic-versus-Clifford thresholds and analytic motifs.\\
5449 III & Temporary nonlinearity in reversible circuits & Affine targets with or without Toffoli-assisted defects.\\
5450 IV & Gate-set distortion and catalytic holonomy & Abstract subgroup, groupoid, and vector-cost theory.\\
5451 V & Spherical collapse and transition holonomy & Packet refinement, Latin-square holonomy, and realization fibers.\\
5452 VI & Algebraic defect loci & Word varieties, codimension, border catalysis, and point counts.\\
5453 VII & Root-system catalytic complexity & Chevalley commutators and thresholds beyond type $A$.\\
5454 \bottomrule
5455 \end{longtable}
5456 
5457 \subsection{Software roadmap}
5458 Version $0.1$ of the atlas supports exact small finite groups.  A mature package should add:
5459 \begin{enumerate}
5460 \item generic multiobjective Dijkstra search;
5461 \item disk-backed and parallel BFS;
5462 \item SAT and SMT export;
5463 \item group action and orbit classification;
5464 \item symbolic word-map elimination;
5465 \item circuit diagrams in Quantikz and SVG;
5466 \item architecture graphs and routing costs;
5467 \item certificate verification independent of the search engine;
5468 \item a machine-readable theorem-status ledger.
5469 \end{enumerate}
5470 
5471 \subsection{Standards for claims}
5472 A result should be labeled \emph{proved} only when every lower bound and restoration claim has a proof.  A complete finite census should identify the state quotient, enumerate its full size, and make the traversal reproducible.  A symbolic skeleton should be valued as a research object but not described as an established shortcut.
5473 
5474 \subsection{Potential applications}
5475 If developed, the theory may contribute to:
5476 \begin{itemize}
5477 \item exact and heuristic quantum circuit compilers,
5478 \item architecture-aware routing,
5479 \item parity and phase-network synthesis,
5480 \item stabilizer and Clifford optimization,
5481 \item reversible arithmetic,
5482 \item Gaussian and fermionic simulation,
5483 \item lower-bound methodology,
5484 \item geometric group theory of gate sets,
5485 \item algebraic geometry of circuit word maps.
5486 \end{itemize}
5487 The near-term value is methodological and algorithmic.  Hardware benefit requires a device-specific cost and noise model.
5488 
5489 \subsection{Twenty central open problems}
5490 \begin{enumerate}
5491 \item Prove or refute a universal six-dimensional linear threshold over all coefficient rings.
5492 \item Determine the true asymptotic order of the maximum unitriangular defect.
5493 \item Decide whether multiplicative distortion is bounded.
5494 \item Determine the lower border length of the canonical six-row atom.
5495 \item Classify tree-tight catalytic matroids.
5496 \item Find a one-copy rigid target with tensor activation.
5497 \item Extend the two-qubit analytic orbit certificate to larger Clifford systems.
5498 \item Analytically classify the three-qubit total-count Clifford defects.
5499 \item Determine whether SWAP restores rigidity for all $n$ in the chosen primitive model.
5500 \item Find the first affine target shortened by temporary nonlinearity, or prove none exists.
5501 \item Find the first diagonal target improved by non-diagonal Clifford catalysis.
5502 \item Determine a phase-polynomial Pareto defect.
5503 \item Find a number-conserving Gaussian target shortened by Bogoliubov escape.
5504 \item Find a matchgate routing catalyst with a certified architecture advantage.
5505 \item Establish a symmetry-sector microscopic-escape theorem.
5506 \item Classify when a fixed number of dirty ancillas gives unbounded saving.
5507 \item Develop typed Green-kernel lower bounds that avoid full enumeration.
5508 \item Determine finite moment bounds sufficient for transition-holonomy classification.
5509 \item Classify catalytic motifs in $B_2$, $C_2$, and $G_2$.
5510 \item Prove a general theorem connecting algebraic codimension and catalytic defect.
5511 \end{enumerate}
5512 
5513 \subsection{Closing perspective}
5514 The common phenomenon is not that every restriction can be beaten.  It is that the path space matters.  A target may obey a symmetry, flag, degree bound, locality rule, or factorization constraint while the cheapest route to that target does not.
5515 
5516 The disciplined research question is therefore:
5517 \begin{center}
5518 \fbox{\parbox{.90\textwidth}{\centering
5519 Which temporary resources can be opened, reused, and exactly removed at a net computational gain?}}
5520 \end{center}
5521 The established linear theory answers this question completely for one important model.  The monograph supplies the symbolic and computational machinery to ask it across quantum gate logic without conflating identities, experiments, and theorems.
5522