Stabilizer Cut Rank Defines Canonical Submodular CD Object¶

Claim/Theorem¶

Let \(Q\) be the qubit set of a stabilizer space \(\mathcal S\), and define

\[ \lambda_{\mathcal S}(L):=\chi_L(\mathcal S) \qquad \text{for every }L\subseteq Q. \]

Then \(\lambda_{\mathcal S}\) is a canonical integer-valued symmetric submodular function on \(Q\).

More explicitly, for every \(A,B\subseteq Q\),

\[ \lambda_{\mathcal S}(A)=\lambda_{\mathcal S}(Q\setminus A), \]

and

\[ \lambda_{\mathcal S}(A)+\lambda_{\mathcal S}(B) \;\ge\; \lambda_{\mathcal S}(A\cap B)+\lambda_{\mathcal S}(A\cup B). \]

Therefore the directly submodular demand object

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

is already canonical and presentation-invariant. Combined with [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]], every measurement-free SWAP-only syndrome-extraction circuit \(C\) for \(\mathcal S\) satisfies

\[ \operatorname{serv}_L(C)\;\ge\;\frac{1}{16}\,\lambda_{\mathcal S}(L) \qquad \text{for every hardware cut }L. \]

So the remaining compiler-native frontier is no longer the existence of a richer CD object. It is the theorem-level step that turns this canonical symmetric submodular demand into a congestion, path, or decomposition statement of the desired CD(T_n,\mathfrak G) form.

Proof sketch:

By [[cross-cut-stabilizer-rank-rank-formula.md]], if \(H\) is any full-row-rank stabilizer matrix for \(\mathcal S\) and \(M_{\mathcal S}\) is its column matroid with rank function \(r\), then

\[ \lambda_{\mathcal S}(L) = r(L)+r(Q\setminus L)-r(Q). \]

So \(\lambda_{\mathcal S}\) is exactly the standard matroid connectivity function of \(M_{\mathcal S}\). 2. Symmetry is immediate from the formula. 3. For submodularity, compute

\[ \lambda_{\mathcal S}(A)+\lambda_{\mathcal S}(B) -\lambda_{\mathcal S}(A\cap B)-\lambda_{\mathcal S}(A\cup B) \]

as

\[ \bigl[r(A)+r(B)-r(A\cap B)-r(A\cup B)\bigr] + \bigl[r(A^c)+r(B^c)-r(A^c\cap B^c)-r(A^c\cup B^c)\bigr]. \]

Each bracket is nonnegative by submodularity of the matroid rank function \(r\), so the whole expression is nonnegative. 4. [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]] gives the service inequality cut by cut, hence \(T_{\mathrm{sub}}(\mathcal S)\) is already a canonical compiler-side lower-bound object in the measurement-free SWAP-only regime. 5. This also cleanly separates the three representation options now on disk: - [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]] rules out exact packaging by an ordinary weighted graph on qubit coordinates in general; - the same four-qubit example is representable by a single hyperedge on all four qubits, so hypergraph cut models are strictly more expressive than ordinary graph cuts on the same ground set; - directly submodular packaging always exists canonically, without choosing any hyperedge or auxiliary-vertex realization.

As an optional structural corollary, [[linked-branch-decomposition-exists-at-optimal-width.md]] now applies directly to \(\lambda_{\mathcal S}\): there is an optimal-width linked branch decomposition of this intrinsic demand function.

Dependencies¶

[[cross-cut-stabilizer-rank-rank-formula.md]]
[[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]]
[[stabilizer-cut-rank-is-not-a-graph-cut-function.md]]
[[linked-branch-decomposition-exists-at-optimal-width.md]]

Conflicts/Gaps¶

This gives a canonical directly submodular CD object, not yet a packet-routing theorem or a guest graph with explicit paths.
The hypergraph remark is only a separation-of-expressivity observation. It does not prove that every stabilizer cut-rank function is a hypergraph cut function, nor that any such representation would be canonical.
The auxiliary-vertex graph option also remains open as a possible realization trick, but it is no longer needed to define the intrinsic demand object itself.
None of this by itself proves linear balanced-cut rank for the explicit Quantum Tanner parity-check matroids.

Sources¶

10.48550/arXiv.2109.14599
10.1109/TIT.2009.2030492
10.1006/jctb.2001.2082