9.11 Discussion and open problems
On this page · Permalink · Source line 3001
9.11.1 What the threshold and higher families establish
On this page · Permalink · Source line 3003
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.
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.
9.11.2 Relation to ordinary CNOT synthesis
On this page · Permalink · Source line 3009
Exact CNOT synthesis usually minimizes \({\ell_{*}}\) on all of \({\operatorname{GL}}_n({\mathbb 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 [25], [44], [43]. 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.
The 2026 NP-completeness result for all-to-all CNOT distance shows that cancellation and unrestricted parity reuse must be handled in full generality [18]. The present constructions isolate explicit reusable-carrier mechanisms under an ordered restriction. They do not resolve ambient synthesis complexity.
9.11.3 Open directions
On this page · Permalink · Source line 3015
Question 9.57: Universal six-dimensional threshold
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 \({\mathbb F}_2\) and \({\mathbb F}_3\).
Question 9.58: Geometry of the defect locus
For fixed \(n\) and \(d\), determine the irreducible components and exact dimension of \(\overline{\mathcal D_{n,\ge d}}\). When is the lower bound \({\operatorname{codim}}\ge d\) sharp?
Question 9.59: Border catalysis
Does the canonical atom have lower border product length six or seven? More generally, when can exact catalytic defects disappear under algebraic degeneration?
Question 9.60: Correct growth of the maximum defect
Is \(D_n({\mathbb F})\) of order \(n\log n\), or can interacting catalysts produce a larger power of \(n\)? The current bounds are
Question 9.61: Multiplicative distortion
Is
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.
Question 9.62: Exact ambient complexity of snapshot targets
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.
Question 9.63: Tensor synergy and activation
Can \(A\otimes B\) admit an ambient circuit shorter than the lifted bound
Such synergy would only increase the defect, but understanding it is necessary for exact tensor complexity. Does there exist a tree-tight target with \({\Delta}(A)=0\) but \(\kappa_\otimes(A)>0\)?
Question 9.64: Higher catalytic normal forms
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.
Question 9.65: Two-gate multiplicative ceiling
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.
Question 9.66: Matroidal classification
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.
Question 9.67: Weighted phase transition
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.
Question 9.68: Other root systems
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?
Question 9.69: Certificate extraction
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.