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.

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