Lesson 04 - Stabilizer Cut Rank and Matroid Connectivity

Goal

Learn the invariant cut demand object for stabilizer measurements: cross-cut stabilizer rank. Then learn why its matrix formula turns the frontier into a binary matroid connectivity problem.

Prerequisites And Diagnostic Checks

1. What is a stabilizer group or stabilizer space?
2. Why can different generating sets define the same stabilizer space?
3. What is the rank of a binary matrix over GF(2)?
4. What is a quotient space?

Concrete Motivation

The naive Tanner cut count asks:

how many chosen generators touch both sides of a cut?

That is not invariant. A generator set can be changed by multiplying stabilizers together. Some crossing generators may be replaced by products that live on one side, and some non-crossing-looking descriptions may hide a real cross-cut stabilizer constraint.

The invariant question is:

how much stabilizer information cannot be generated separately on the two sides?

That quantity is \(\chi_L(\mathcal S)\).

Worked Example Before Abstraction

Let \(\mathcal S\) be a stabilizer space on qubits \(Q=L\sqcup R\).

Define:

• \(\mathcal S_L\): stabilizers supported entirely inside \(L\);
• \(\mathcal S_R\): stabilizers supported entirely inside \(R\).

If every stabilizer can be generated from these two local subspaces, then the cut carries no intrinsic stabilizer demand:

\[ \mathcal S=\mathcal S_L+\mathcal S_R. \]

If not, the quotient measures what remains:

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

This number is independent of the generator list. It is a property of the stabilizer space and the qubit cut.

Formal Definition And Rank Formula

The local graph nodes are:

• cross-cut-stabilizer-rank.md
• cross-cut-stabilizer-rank-rank-formula.md
• stabilizer-cut-rank-functional.md

For a full-row-rank binary stabilizer support matrix split by columns:

\[ H=[H_L\mid H_R], \]

the rank formula is:

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

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

So the frontier becomes concrete:

prove that the relevant Quantum Tanner stabilizer matrix has linear matroid connectivity across every hardware-balanced qubit cut.

Hardware Functional

The stabilizer cut-rank functional packages code demand and hardware separator size:

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

If a cut has large \(\chi_L\) and the hardware has a small boundary, the circuit must spend depth serving that cut.

Conjecture Linkage

This lesson is the hinge between the old expander intuition and the current intrinsic frontier.

The old version:

many Tanner checks cross the cut.

The current intrinsic version:

the stabilizer space has large quotient dimension across the cut.

For Conjecture 3, this matters because only the second statement is immune to generator changes.

What This Does And Does Not Prove

This proves:

• the definition of the invariant cut quantity;
• the rank formula;
• the reduction from stabilizer cut rank to binary matroid connectivity.

This does not prove:

• that Quantum Tanner matrices have linear balanced cut rank;
• that all good QLDPC codes have large cut rank;
• that matroid connectivity automatically has classical routing semantics.

The graph explicitly warns against those leaps:

• good-code-parameters-do-not-imply-cut-rank.md
• good-ltc-does-not-imply-balanced-cut-rank.md

Active Recall

1. Define \(\chi_L(\mathcal S)\) without mentioning a generator list.
2. Derive the rank formula in words.
3. Why is this a matroid connectivity function?
4. Why do good parameters alone not imply large \(\chi_L\)?
5. What exact Quantum Tanner theorem would close the intrinsic cut-rank route?

Next-Step Handoff

Next lesson: learn how stabilizer cut rank becomes a compiler lower bound in the SWAP-only service model, and why token crossing was the wrong picture.