Skip to content

Lesson 06 - Why Classical Routing Semantics Fail

Goal

Understand why the current graph does not identify stabilizer cut rank with ordinary graph cuts, packet routing, or terminal hypergraph cuts, even though binary matroids admit an exact graph cut-rank realization.

Prerequisites And Diagnostic Checks

  1. What is the difference between edge-cut capacity and cut rank?
  2. Why is a nonnegative graph or hypergraph cut a classical routing-like object?
  3. What is a basis of a binary matroid?
  4. What does pivot or basis dependence mean informally?

Concrete Motivation

The compiler dream is:

turn a stabilizer family into a demand graph, then apply congestion-dilation lower bounds.

The graph now says this dream is too naive. Stabilizer cut rank is intrinsic and submodular, but ordinary graph-cut capacity cannot represent it in general.

That does not mean everything fails. It means the semantics must be chosen carefully.

Worked Example Before Abstraction

Take the all-\(Z\) stabilizer on four qubits. Its cut-rank function can have value \(1\) across every nonempty proper cut. Ordinary nonnegative graph cuts cannot represent that pattern on the same terminal set. If every nontrivial cut has the same positive capacity, graph cut constraints force incompatible edge weights.

This is the lesson of:

So the first naive idea fails:

stabilizer cut rank is not ordinary weighted graph cut capacity.

Binary Matroid Positive Result

There is still an exact graph-theoretic realization:

For a binary matroid \(M\) and a chosen basis \(B\), the fundamental graph satisfies:

\[ \lambda_M(X)=\operatorname{cutrk}_{G_{\mathrm{fund}}(M,B)}(X)+1. \]

This is powerful. It says stabilizer cut rank can be realized as graph cut rank over GF(2).

But graph cut rank is not edge capacity. It is algebraic.

Why This Still Does Not Give Routing

The classical interpretation breaks in several ways.

First, edge cuts of fundamental graphs are basis-unstable:

Different bases can give fundamental graphs with the same exact matroid connectivity but very different ordinary edge-cut sizes.

Second, basis-robust local gadgetizations fail:

Third, nonnegative hypergraph terminal semantics fail even for simple binary examples:

Fourth, generic submodular demand is too broad:

Conjecture Linkage

This lesson prevents a common wrong move:

We have an intrinsic cut function, so surely there is an ordinary demand graph.

The current graph says no. The correct statement is narrower:

  • intrinsic submodular cut demand exists;
  • exact binary cut-rank graph realization exists;
  • ordinary terminal routing semantics remain open or false depending on the target formulation.

What This Does And Does Not Prove

This proves:

  • ordinary graph cuts do not generally represent stabilizer cut rank;
  • fundamental graph cut-rank is exact but algebraic;
  • several natural conversions to classical routing fail.

This does not prove:

  • no auxiliary-variable construction exists;
  • no approximate semantics can ever be useful;
  • no family-specific routing theorem can exist for Quantum Tanner codes.

The point is precision: any future CD theorem must say exactly which semantics it uses.

Active Recall

  1. What is the difference between cut capacity and cut rank?
  2. Why does the fundamental graph theorem not close classical routing?
  3. What does basis instability rule out?
  4. Why are nonnegative terminal hypergraphs still too restrictive?
  5. What remains possible after these failures?

Next-Step Handoff

Next lesson: study the intrinsic matroid route, where the target is no longer classical routing semantics but dense original-matroid connectivity.