Lesson 05 - Submodular CD and SWAP-Only Service

Goal

Understand the current compiler-native result: stabilizer cut rank defines a canonical submodular demand object, and SWAP-only measurement-free circuits must provide cut-edge service proportional to that demand.

Prerequisites And Diagnostic Checks

1. What is a SWAP-only compilation model?
2. What is the difference between moving a qubit token and applying a cross-cut gate?
3. What does it mean for a set function to be symmetric and submodular?
4. Why does a cut lower bound naturally lead to a congestion-like quantity?

Concrete Motivation

The old mental model was:

if a stabilizer crosses a cut, then some qubit token must cross the hardware cut.

That is false. A cross-cut interaction can serve a stabilizer without any token permanently crossing. The local graph has an explicit node for this failure:

• token-crossing-extraction-fails-for-swap-only-compilation.md

But the lower-bound route survives after changing the service notion.

The correct replacement is:

the circuit must provide enough cross-cut gate service to create or measure the required cross-cut stabilizer information.

Worked Example Before Abstraction

Consider a stabilizer such as \(Z_1Z_2\) with qubit \(1\) on the left and qubit \(2\) on the right. A circuit can measure it by bringing an ancilla to interact across the cut, or by applying a cross-cut CNOT-like service, without requiring the data qubit token itself to move to the other side.

So "token crossing" is too strict.

However, the hardware cut still has to be used. A cross-cut stabilizer cannot be served using only gates entirely on the left and entirely on the right. Something must couple the two sides.

That is the service principle.

Formal Compiler Layer

The relevant nodes are:

• cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md
• stabilizer-cut-rank-defines-canonical-submodular-cd-object.md
• submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md
• swap-only-compiler-extraction-reduces-cd-to-stabilizer-cut-rank.md

Define:

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

This is a canonical symmetric submodular function on qubit subsets. It defines the submodular demand object:

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

Then define the submodular cut congestion against hardware \(G_{\mathrm{hw}}\):

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

The current theorem says SWAP-only measurement-free syndrome-extraction circuits have depth lower-bounded, up to constants, by this submodular cut congestion.

Conjecture Linkage

This is the best current replacement for a classical CD(T_n,G) theorem.

It settles a real compiler-native formulation:

• demand is intrinsic stabilizer cut rank;
• hardware bottleneck is cut boundary size;
• circuit cost is cross-cut service depth.

But it is not yet the same as the original classical-routing intuition. It is a submodular cut-functional theorem, not a packet-routing theorem.

What This Does And Does Not Prove

This proves:

• token crossing is the wrong primitive;
• service is the right SWAP-only primitive currently on disk;
• stabilizer cut rank defines a canonical submodular demand object;
• submodular cut congestion lower-bounds SWAP-only depth in the stated model.

This does not prove:

• every stabilizer demand has a classical guest graph;
• every demand decomposes into routed packets;
• every submodular demand has meaningful path semantics;
• the full original CD(T_n,G) wording if that wording requires classical routing.

Active Recall

1. Give a two-qubit reason token crossing is false.
2. What is cross-cut service?
3. Define \(T_{\mathrm{sub}}\).
4. Why is \(CD_{\mathrm{sub}}\) a theorem-level object while classical CD remains open?
5. Which model restrictions are still present?

Next-Step Handoff

Next lesson: learn why attempts to turn stabilizer cut rank into ordinary graph cuts, packets, or hypergraph terminal cuts fail.