Skip to content

04 - Intrinsic Matroid and Route-D Frontier

Learning Target

After this chapter, you should be able to state the two main remaining frontier directions: intrinsic original-matroid connectivity and compiler semantics beyond submodular CD.

Intrinsic Route

The intrinsic route tries to prove large balanced cut rank directly in the original qubit parity-check matroid:

\[ \chi_L(\mathcal S_n)=\Omega(n) \]

for every hardware-balanced cut \(L\).

If this holds, then the stabilizer cut-rank functional is large on low-separator hardware, and the submodular CD lower bound applies.

The current graph compresses the broad intrinsic target into dense original-matroid concentration, especially dense tangle breadth:

the original qubit parity-check matroid has a high-order tangle whose breadth is dense enough to force linear connectivity on every balanced cut.

This is a sufficient target. It is not yet proved for the target Quantum Tanner families.

Why Generic Matroid Theory Is Not Enough

The graph has stress-tested several generic routes:

  • high tangle order;
  • grid-minor domination;
  • robust/nonsequential flower structure;
  • tester-side local agreement and irreducibility;
  • lean or linked decompositions.

The result is not that these theories are irrelevant. The result is that generic versions stop before the required dense original-qubit concentration.

The graph currently reduces intrinsic progress to three family-specific lift theorems:

  1. grid domination to dense original-matroid concentration;
  2. robust flower template exclusion or concentration on balanced cuts;
  3. tester-side irreducibility to exact original-qubit matroid connectivity.

Any future intrinsic breakthrough must add a genuinely family-specific theorem of this kind or a sharper replacement.

Local-Block Rank Accumulation

The most concrete Quantum Tanner route uses local row blocks. Let:

\[ S=\operatorname{rowspan}H, \qquad S(v)=\operatorname{rowspan}H(v). \]

For a cut \(L\sqcup R=Q\), set:

\[ B(L)=S_L+S_R. \]

The local quotient image is:

\[ W_v(L)=\frac{S(v)+B(L)}{B(L)}. \]

The key identity is:

\[ \chi_L(S) = \dim\left(\sum_v W_v(L)\right). \]

This splits the missing theorem into two losses:

  • survival loss: local cross-cut classes die in the global quotient;
  • overlap loss: surviving local images fail to be independent.

So many crossed local neighborhoods are not enough. One needs linearly many independent quotient images.

Route D: Compiler Semantics

The compiler-native side asks whether stabilizer cut rank can be given a classical or auxiliary-variable routing meaning beyond submodular CD.

The current graph says:

  • ordinary terminal graph or hypergraph semantics fail in explicit examples;
  • hidden-variable graph-cut realizations can be more expressive;
  • exact hidden-variable expressibility still does not automatically imply compiler meaning.

This makes Route D a semantic frontier. The question is not just whether some auxiliary representation exists. The question is whether that representation corresponds to a physical routing, packet, service, or lower-bound mechanism.

Practical Research Handoff

After completing the course, choose one of three next targets.

Target A: manuscript packaging of the solved static theorem.

Target B: intrinsic Quantum Tanner cut rank.

  • Try to prove a family theorem controlling local quotient-image survival and overlap, or dense original-matroid concentration.

Target C: compiler semantics.

  • Try to sharpen whether auxiliary-variable representations can or cannot mean routing.

Do not widen the whole graph by default. Pick one target and load only its nodes.

Active Recall

  1. What would linear balanced cut rank prove for the Conjecture 3 route?
  2. Why is dense tangle breadth only a sufficient target, not a proved fact?
  3. What are survival loss and overlap loss?
  4. Why is Route D a semantic frontier?
  5. Which target would you pick next: A, B, or C?

Source Spine