Five-Qubit Stabilizer Cut Rank Is Hidden-Vertex Graph-Cut Representable¶

Claim/Theorem¶

Let Q={1,2,3,4,5} and let \mathcal S be any stabilizer space on Q. Define the associated 5-ary Boolean cost function

\[ f_{\mathcal S}(x_1,\dots,x_5):=\chi_{L_x}(\mathcal S), \qquad L_x:=\{i\in Q:x_i=1\}, \]

where \chi_L(\mathcal S) is the intrinsic cut-rank functional from [[cross-cut-stabilizer-rank-rank-formula.md]].

Then f_{\mathcal S} is expressible by binary submodular functions with auxiliary variables, equivalently by a hidden-vertex graph-cut reduction to s,t-Min-Cut.

More concretely, every 5-qubit stabilizer cut-rank function admits a decomposition

$$ f_{\mathcal S}

= m + \sum_j \lambda_j \phi_j, \qquad \lambda_j\ge 0, $$

where m is modular and each \phi_j is a Boolean upper or lower fan in the sense of Živný-Cohen-Jeavons, Definition 5 (p. 3351). By Example 7 (p. 3351) these fans have explicit Boolean polynomial forms, and by Theorem 8 (p. 3352) every fan is expressible by binary submodular functions using auxiliary variables. Since modular functions are linear and hence already binary submodular on the Boolean domain, the whole decomposition is expressible over \Gamma_{\mathrm{sub},2}.

This is a derived finite theorem from exhaustive exact computation:

Enumerate all 374 subspaces of GF(2)^5.
For each subspace, form the connectivity function L\mapsto \chi_L(\mathcal S) using [[cross-cut-stabilizer-rank-rank-formula.md]].
Deduplicate these to 92 distinct functions on 2^Q.
Enumerate all distinct 5-ary Boolean upper and lower fan functions from Definition 5.
For each of the 92 stabilizer functions, solve the linear feasibility problem

\[ f = m + \sum_j \lambda_j \phi_j \]

with \lambda_j\ge 0, \phi_j ranging over the 5-ary fans, and m ranging over all modular Boolean functions. 6. Reconstruct exact rational certificates from the feasible LP solutions; all 92 cases admit exact rational decompositions, with reconstructed denominators at most 36.

Consequences for the current frontier:

there is no 5-qubit stabilizer-space counterexample to ordinary hidden-vertex graph-cut representability;
the stronger 5-qubit result now upgrades [[five-qubit-stabilizer-cut-rank-satisfies-fsep.md]] from a necessary-condition pass to an actual positive expressibility theorem;
the binary 5-qubit example from [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]] still blocks exact nonnegative hypergraph semantics, but it no longer threatens the hidden-vertex graph-cut route;
any negative theorem against ordinary hidden-vertex graph-cut realizability inside the stabilizer subclass must therefore start at arity at least 6.

Dependencies¶

[[cross-cut-stabilizer-rank-rank-formula.md]]
[[five-qubit-stabilizer-cut-rank-satisfies-fsep.md]]
[[four-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]]
[[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]]

Conflicts/Gaps¶

This is an exact finite theorem only for arity 5. It does not decide whether some 6-qubit or larger stabilizer cut-rank function fails hidden-vertex graph-cut expressibility.
The proof is currently existential rather than gadget-explicit: it produces exact rational modular-plus-fan decompositions, not a compact hand-written gadget family for every 5-qubit stabilizer space.
The result still lives at the level of auxiliary-variable graph-cut expressibility. It does not yet yield routing-style CD(T_n,G) semantics on the physical qubit set.
The positive result is derived computation, not a literature theorem stated verbatim in the cited papers.

Sources¶

10.1016/j.dam.2009.07.001
10.48550/arXiv.2109.14599