Skip to content

03 - Stabilizer Cut Rank and Submodular CD

Learning Target

After this chapter, you should be able to explain the current invariant demand object for Conjecture 3 and why it leads to submodular CD, not automatically to ordinary packet routing.

From Crossing Checks To Cross-Cut Rank

A chosen generator crossing a cut is not an invariant object. Stabilizer generators can be multiplied, replaced, and reorganized without changing the stabilizer space.

The invariant question is:

how much stabilizer information cannot be generated separately on the left and right sides of the cut?

For a stabilizer space \(\mathcal S\) and qubit cut \(Q=L\sqcup R\), define \(\mathcal S_L\) and \(\mathcal S_R\) as the subspaces supported entirely on \(L\) and \(R\). Then:

\[ \chi_L(\mathcal S) = \dim \frac{\mathcal S}{\mathcal S_L+\mathcal S_R}. \]

This is cross-cut stabilizer rank.

For a full-row-rank binary support matrix \(H=[H_L\mid H_R]\), the graph records the rank formula:

\[ \chi_L(\mathcal S) = \operatorname{rank}(H_L)+\operatorname{rank}(H_R)-\operatorname{rank}(H). \]

This is the connectivity function of the column matroid of \(H\).

The Hardware Functional

Once \(\chi_L\) is the demand across a cut, the hardware bottleneck is the number of hardware edges across the same cut. This gives a cut ratio:

\[ \frac{\chi_L(\mathcal S)}{|\partial_{G_{\mathrm{hw}}}L|}. \]

Taking the maximum over cuts gives the stabilizer cut-rank functional used in the graph:

\[ \Xi(\mathcal S,G_{\mathrm{hw}}) = \max_L \frac{\chi_L(\mathcal S)}{|\partial_{G_{\mathrm{hw}}}L|}. \]

This is the invariant replacement for raw crossing-generator counts.

Why Token Crossing Was False

The first compiler intuition said that a cross-cut stabilizer forces a data qubit token to cross the hardware separator. That is too strong. A circuit can provide cross-cut gate service without permanently moving a token across the cut.

The local graph therefore rejects token crossing but keeps service:

  • token crossing is false;
  • cross-cut service remains a lower-bound primitive in the SWAP-only measurement-free model.

This distinction matters because it saves the lower-bound route while correcting the mechanism.

Submodular Demand Object

Define:

\[ \lambda_{\mathcal S}(L)=\chi_L(\mathcal S). \]

This is a canonical symmetric submodular function on qubit subsets. The current graph packages it as:

\[ T_{\mathrm{sub}}=(Q,\lambda_{\mathcal S}). \]

Against hardware \(G_{\mathrm{hw}}\), define:

\[ CD_{\mathrm{sub}}(T_{\mathrm{sub}},G_{\mathrm{hw}}) = \max_L \frac{\lambda_{\mathcal S}(L)}{|\partial_{G_{\mathrm{hw}}}L|}. \]

The graph contains a theorem-level lower bound from this object to SWAP-only service depth.

Why This Is Not Ordinary Routing

Stabilizer cut rank is not generally an ordinary nonnegative graph cut on the physical qubits. Binary matroids do admit an exact graph realization by fundamental graph cut-rank:

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

but graph cut-rank is algebraic over GF(2), not edge capacity. Ordinary edge-cut readings are basis-unstable, and terminal nonnegative hypergraph semantics fail in explicit binary examples.

So the safe current statement is:

submodular CD is theorem-backed; classical routing CD remains a semantic frontier.

Active Recall

  1. Define \(\chi_L(\mathcal S)\) and give the rank formula.
  2. Why is \(\chi_L\) better than counting chosen crossing generators?
  3. Why does token crossing fail but cut service survive?
  4. Define \(T_{\mathrm{sub}}\) and \(CD_{\mathrm{sub}}\).
  5. Why does fundamental graph cut-rank not close packet routing?

Source Spine