Skip to content

SWAP-Only Compiler Extraction Reduces CD To Stabilizer Cut Rank

Claim/Theorem

The present gap between the stabilizer-measurement lower bounds and a compiler-native CD(T_n,\mathfrak G) theorem can be isolated to one missing reduction.

Delfosse, Beverland, and Tremblay prove in Theorem 1 (p. 2), and [[stabilizer-cut-rank-functional.md]] repackages cut by cut, that inside the local-Clifford stabilizer-measurement model one has

\[ \operatorname{depth}(C)=\Omega\!\bigl(\Xi(\mathcal S,G_{\mathrm{hw}})\bigr), \qquad \Xi(\mathcal S,G_{\mathrm{hw}}) = \max_L \frac{\chi_L(\mathcal S)}{|\partial L|}. \]

Leighton, Maggs, and Rao prove in Theorem 3.4 (p. 174) that once a SWAP-only implementation has been converted into a packet-routing instance with edge-simple paths, routing depth is Omega(c+d), hence at least Omega(c). Therefore a first attempt at a full SWAP-only compiler-native lower bound is the following execution-graph extraction lemma:

for every SWAP-only compilation E of one syndrome round for stabilizer space \mathcal S on hardware graph G_{\mathrm{hw}}, one can extract a multiset P(E) of edge-simple token paths in G_{\mathrm{hw}} such that

  • each extracted path has length O(depth(E)), and
  • for every hardware cut L, the total number of extracted path traversals across \partial L is Omega(\chi_L(\mathcal S)).

If such a lemma held, then some edge of \partial L would carry load Omega(\chi_L(\mathcal S)/|\partial L|), so Theorem 3.4 would imply

\[ \operatorname{depth}(E) = \Omega\!\left(\max_L \frac{\chi_L(\mathcal S)}{|\partial L|}\right) = \Omega\!\bigl(\Xi(\mathcal S,G_{\mathrm{hw}})\bigr). \]

If this token-traversal lemma were true, it would close the routing side of the compiler-native bridge.

However, [[token-crossing-extraction-fails-for-swap-only-compilation.md]] now shows that the literal token-traversal form is false even for a single nearest-neighbor cross-cut stabilizer. The replacement service-based statement is now partially recovered: [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]] shows, by a direct sharpening of the Delfosse proof, that measurement-free SWAP-only compilers already obey \operatorname{serv}_L(C)=\Omega(\chi_L(\mathcal S)) on every cut. Meanwhile [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]] rules out exact packaging by an ordinary weighted graph on the qubit set, while [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]] shows that the intrinsic cut-rank function itself is already a canonical symmetric submodular demand object. The cut-functional theorem is therefore no longer missing: [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]] packages it into a bona fide compiler-native lower bound for measurement-free SWAP-only circuits. Finally, [[generic-submodular-demand-does-not-force-classical-routing-realization.md]] and [[matroid-connectivity-does-not-force-hypergraph-approximation.md]] show that neither generic symmetric-submodular theory nor generic matroid connectivity is enough to produce a classical routing realization, [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]] shows that the binary or stabilizer subclass does admit an exact graph realization, but only via graph cut-rank, [[fundamental-graph-edge-cuts-are-basis-unstable.md]] shows that even this exact graph realization does not descend stably to ordinary edge-cut capacity on the same graph, [[basis-robust-fundamental-graph-loads-must-be-pivot-invariant.md]] shows that any basis-robust classical load read from a chosen fundamental graph must survive pivoting, [[local-incidence-lifts-of-fundamental-graphs-are-not-pivot-robust.md]] rules out the whole local-incidence gadget route for packet, hypergraph, and auxiliary-vertex interpretations, [[pivot-class-best-incidence-load-still-overestimates-connectivity.md]] shows that even optimizing incidence-local loads over the full pivot class still misses the connectivity scale by a linear factor, [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]] now rules out even exact global nonnegative-hypergraph semantics inside a simple binary-matroid example, [[four-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]] shows that the surviving auxiliary-vertex route is genuinely not a 4-terminal issue, [[five-qubit-stabilizer-cut-rank-satisfies-fsep.md]] shows that the current universal F_{\mathrm{sep}} obstruction still does not separate the stabilizer subclass at 5 terminals, [[boolean-network-generalization-adds-no-nonmonotone-power-for-stabilizer-cut-rank.md]] shows that Iwamasa's broader Boolean network-representability framework adds only monotone functions and therefore collapses back to the original hidden-vertex graph-cut question on every nontrivial stabilizer cut-rank function, [[five-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]] shows that the ordinary hidden-vertex route actually survives through all 5-qubit stabilizer examples, [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]] shows that the first natural constructive extension beyond that boundary already fails at a specific 6-qubit stabilizer space, [[six-qubit-witness-survives-all-four-ary-exact-minors.md]] shows that even the exact arity-4 Sep/F_{\mathrm{sep}} criterion cannot refute that witness after all standard pinning and minimization reductions, [[six-qubit-witness-satisfies-direct-fsep.md]] shows that even the original 6-ary witness itself satisfies the direct higher-arity F_{\mathrm{sep}} condition, [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]] gives an explicit four-hidden-bit realization of that witness, [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]] shows that this threshold-lift realization extends to an infinite binary-matroid/stabilizer family beyond the modular-plus-fan cone, [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]] identifies the exact presentation-invariant structure behind that family: a parallel class attached to a circuit, [[direct-sums-of-threshold-lift-pieces-stay-hidden-vertex-representable.md]] shows that the positive route extends one step further to direct sums of such pieces, [[low-order-gluing-does-not-explain-high-intrinsic-width.md]] shows that 2-sum and 3-sum closure would still remain trapped in the already-classified constant-connectivity regime, [[threshold-lift-plus-direct-sum-class-never-reaches-connectivity-three-core.md]] shows that the present positive class never reaches a connected \chi\ge 3 core at all, [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]] isolates the first natural connected post-gluing test family beyond that boundary, [[multi-parallel-circuit-connected-family-reduces-to-selected-or-selector.md]] reduces one natural route on that family to a ternary selected-OR gadget, [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]] shows that minimizing auxiliary variables in a binary submodular energy preserves visible submodularity, [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]] uses this to prove that the selector itself is not hidden-vertex graph-cut expressible at any auxiliary budget, [[selector-quotient-is-not-a-submodular-minor-of-connected-family.md]] shows why this still does not settle the whole connected family, [[branch-min-route-for-connected-family-fails-at-local-submodularity.md]] closes a second exact route by proving that the alternative factorization \lambda_M=\min(U,1+S) cannot be implemented by one global branch bit plus independent local hidden-vertex gadgets, and [[smallest-connected-multi-parallel-circuit-member-survives-all-four-ary-exact-minors.md]] shows that even the smallest connected member of this family survives every exact 4-ary pinning/minimization minor. So the true remaining bridge is sharper still: either produce a genuinely more global connected hidden-vertex realization beyond these failed exact routes, lift the obstruction by a stronger family-level argument, or explain why even such connected realizations still fail to induce routing-style CD(T_n,G) semantics.

This live gap is now narrower again: [[two-element-multi-parallel-circuit-family-satisfies-direct-fsep.md]] shows that the whole size-2 multi-parallel-circuit subfamily, including the first connected \chi\ge 3 cases, also survives the direct higher-arity F_{\mathrm{sep}} test. So the selector route, the one-branch-bit local factorization route, the exact 4-ary closure route, and the direct F_{\mathrm{sep}} route all fail on the first connected family now on disk. Moreover [[smallest-connected-multi-parallel-circuit-member-has-no-1-or-2-auxiliary-realization-in-large-coefficient-box.md]] shows that even a genuinely global exact quadratic-submodular search with 1 or 2 auxiliaries and coefficients in [-64,64] fails on M_{2,2,2}. If a connected hidden-vertex realization exists there, it already lies beyond the obvious very-low-complexity auxiliary budget.

The constructive gap is narrower on the symmetry side too: [[natural-orbit-symmetric-hidden-vertex-ansatze-fail-on-m222.md]] shows that even two natural symmetry-respecting global ansatz classes fail exactly on M_{2,2,2}, namely one hidden bit per class and one global hidden bit plus one hidden bit per class. So a future positive theorem cannot simply follow the obvious automorphism-respecting hidden architecture of the family.

That obstruction now survives the first hidden-symmetry-breaking extension as well: [[visible-symmetric-hidden-distinguished-ansatze-fail-on-m222.md]] shows that even with three or four fully distinguished hidden bits, the first natural global ansatz classes that still respect only the visible pair symmetries remain infeasible. So any successful constructive theorem must either break even those visible symmetries or use a much richer architecture than the current quadratic ansatz families.

At the same time, the pinned local shadows are now known to be much more positive than the global function itself: [[every-four-ary-pinning-minor-of-m222-is-one-hidden-representable.md]] shows that every 4-ary pinning shadow of M_{2,2,2} already has a one-hidden-bit realization. So any exact k<=2 impossibility theorem for the full connected witness must be genuinely global and cannot be detected on pinned 4-terminal views alone.

That genuinely global boundary is now reached one step later: [[pinned-five-ary-shadows-of-m222-obstruct-one-hidden-realizability.md]] shows that pinned 5-ary shadows already split into one-hidden feasible and infeasible classes, and therefore M_{2,2,2} itself has no one-hidden realization. So the first exact low-auxiliary obstruction appears at arity 5, while k=2 and fully less-symmetric k\ge 3 constructions remain open.

The same bridge cannot be stated unchanged in measurement-assisted or adaptive-classical models. Rosenbaum proves in Theorem 1.1 (p. 2) that 2D CCNTC can simulate arbitrary CCAC circuits with only constant-factor depth overhead, and Corollary 1.4 places controlled-U and fanout in constant depth there. Theorem 1.6 (p. 3) recovers Theta(sqrt(n)) only in the nonadaptive nearest-neighbor model. So any successful CD statement must keep the compiler model in the measurement-free SWAP-only regime or explicitly price the extra adaptive resource.

Dependencies

  • [[stabilizer-cut-rank-functional.md]]
  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[packet-routing-o-c-plus-d.md]]
  • [[nonadaptive-2d-nearest-neighbor-lower-bound.md]]

Conflicts/Gaps

  • The literal token-crossing extraction lemma is now ruled out by [[token-crossing-extraction-fails-for-swap-only-compilation.md]]. For measurement-free SWAP-only compilers, [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]], [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]], and [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]] now settle the canonical cut-functional replacement. The live open problem is only a path, packet, or guest-graph realization of that submodular demand.
  • The quantity \chi_L(\mathcal S) is a rank/connectivity invariant, not obviously a count of pairwise meetings or routed Tanner edges. [[generic-submodular-demand-does-not-force-classical-routing-realization.md]] shows that generic symmetric-submodular theory does not bridge this gap, [[matroid-connectivity-does-not-force-hypergraph-approximation.md]] shows that even generic matroid connectivity is still too broad, [[binary-matroid-connectivity-equals-fundamental-graph-cut-rank.md]] shows that the exact binary specialization lands in graph cut-rank rather than graph cut capacity, [[fundamental-graph-edge-cuts-are-basis-unstable.md]] shows that even ordinary edge cuts of the exact realizing graphs are basis-unstable, [[basis-robust-fundamental-graph-loads-must-be-pivot-invariant.md]] shows that any basis-robust classical load semantics must in fact be pivot-robust, [[local-incidence-lifts-of-fundamental-graphs-are-not-pivot-robust.md]] shows that even the broad local-incidence gadget route fails, [[pivot-class-best-incidence-load-still-overestimates-connectivity.md]] shows that even best-basis optimization over the whole pivot class is still off by a linear factor, [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]] shows that even exact global nonnegative hypergraph cut semantics can already fail in the binary subclass, [[four-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]] and [[five-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]] show that the auxiliary-vertex question still survives through arity 5, [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]] shows that the current modular-plus-fan constructive proof route already fails at arity 6, [[six-qubit-witness-survives-all-four-ary-exact-minors.md]] shows that even all 4-ary pinning/minimization minors of that witness pass the exact Sep/F_{\mathrm{sep}} criterion, [[six-qubit-witness-satisfies-direct-fsep.md]] shows that even the original 6-ary witness still satisfies direct higher-arity F_{\mathrm{sep}}, [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]] shows that this same witness is nevertheless explicitly hidden-vertex graph-cut representable, [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]] and [[parallel-extension-of-binary-circuit-gives-threshold-lift-cut-rank.md]] show that the same threshold-lift pattern is really the invariant circuit-plus-parallel-class case, [[direct-sums-of-threshold-lift-pieces-stay-hidden-vertex-representable.md]] shows that this positive class is at least closed under direct sums, and [[boolean-network-generalization-adds-no-nonmonotone-power-for-stabilizer-cut-rank.md]] shows that the broader Boolean (k,\rho,\sigma) network-representability framework does not enlarge the nonmonotone stabilizer subclass beyond ordinary hidden-vertex graph cuts. But [[low-order-gluing-does-not-explain-high-intrinsic-width.md]] and [[threshold-lift-plus-direct-sum-class-never-reaches-connectivity-three-core.md]] now sharpen the structural picture further: low-order gluing stays in the \chi=1,2 regime, the present positive class never even reaches a connected \chi\ge 3 core, [[multiple-parallel-classes-on-one-circuit-give-connected-cut-rank-at-least-three-family.md]] shows that the first natural connected post-gluing regime already appears as soon as one replaces several circuit elements by parallel classes, [[multi-parallel-circuit-connected-family-reduces-to-selected-or-selector.md]] shows that one natural compression of that regime collapses to a selected-OR gadget, [[minimizing-hidden-binary-submodular-energy-preserves-submodularity.md]] shows that visible non-submodularity survives every auxiliary-minimization attempt, [[selected-or-selector-is-not-hidden-vertex-graph-cut-expressible.md]] proves that this gadget is not hidden-vertex expressible at any auxiliary budget, [[selector-quotient-is-not-a-submodular-minor-of-connected-family.md]] shows that this still does not descend to the full connected family by any standard closure-preserving minor operation because the original family stays submodular while the quotient does not, and [[branch-min-route-for-connected-family-fails-at-local-submodularity.md]] shows that the alternative exact factorization \lambda_M=\min(U,1+S) also fails in its obvious local-gadget form because the required branch gadget is visibly non-submodular. So the current gap is now even more specific: one must decide hidden-vertex representability or nonrepresentability exactly on such genuinely connected \chi\ge 3 families by a more global argument than either the selector quotient or the one-branch-bit local factorization. Any positive routing theorem must therefore extract substantially more than mere witness-level or family-level binary representability, any local rewrite of one chosen basis graph, any monotone optimization of such local models across all bases, any exact terminal hypergraph cut model, any mere modular-plus-fan decomposition, any exact 4-ary minor test, any direct F_{\mathrm{sep}} test, any direct-sum closure theorem, any low-order gluing theorem, any selected-OR compression, any one-branch-bit local factorization, or any broader Boolean network encoding in Iwamasa's sense, while any negative theorem must use a genuinely different higher-arity obstruction or a witness outside this threshold-lift-plus-direct-sum class.
  • The reduction no longer lacks either a canonical intrinsic demand object or a cut-functional compiler theorem: [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]] and [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]] provide those. What remains open is only a routing-style realization by paths, packets, or a more classical guest graph.
  • Rosenbaum's adaptive upper bound is a model-boundary warning, not a counterexample inside the SWAP-only regime.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1007/BF01215349
  • 10.48550/arXiv.1205.0036