Boolean Network Generalization Adds No Nonmonotone Power For Stabilizer Cut Rank¶

Claim/Theorem¶

Let Q be a qubit set, let \mathcal S be a stabilizer space on Q, and define the Boolean cost function

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

Assume f_{\mathcal S} is not identically zero.

Then the following are equivalent:

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.
f_{\mathcal S} is classically network representable on {0,1}^{|Q|} in the Kolmogorov-Zabih / Živný-Cohen-Jeavons sense.
f_{\mathcal S} is generalized (k,\rho,\sigma)-network representable on {0,1}^{|Q|} in the sense of Iwamasa for some k,\rho,\sigma.

So for nontrivial stabilizer cut-rank functions, Iwamasa's broader Boolean network-representability framework adds no extra positive power beyond the original hidden-vertex graph-cut route.

More concretely:

Lemma 2.1 (p. 5) of Iwamasa identifies classical Boolean network representability with \langle \Gamma_{\mathrm{sub},2}\rangle, i.e. binary-submodular expressibility with auxiliary variables.
Theorem 3.5 (p. 9) shows that any generalized (k,\rho,\sigma)-network representable Boolean function is either classically network representable or monotone.
Theorem 3.6 (p. 9) sharpens this further: the only extra Boolean classes arising in the generalized framework are the two special (2,\rho^\ast,\sigma_1^\ast) and (2,\rho^\ast,\sigma_2^\ast) forms, which are exactly the monotone add-ons in Theorem 3.5.

For stabilizer cut rank, the monotone escape is unavailable. Indeed, by [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]], the function L\mapsto \chi_L(\mathcal S) is symmetric and satisfies

\[ \chi_\emptyset(\mathcal S)=\chi_Q(\mathcal S)=0. \]

Hence if f_{\mathcal S} were monotone nondecreasing, then for every L\subseteq Q,

\[ 0=\chi_\emptyset(\mathcal S)\le \chi_L(\mathcal S)\le \chi_Q(\mathcal S)=0, \]

so f_{\mathcal S} would be identically zero. The same conclusion holds for monotone nonincreasing functions by reversing inclusions. Therefore any nonzero stabilizer cut-rank function is nonmonotone, and Theorem 3.5 forces

\[ \text{generalized Boolean network representable} \iff \text{classically network representable}. \]

Consequences for the current frontier:

the broader Boolean network-representability framework does not furnish a new positive auxiliary-vertex theorem for stabilizer cut rank beyond the ordinary hidden-vertex graph-cut question;
it also does not furnish a stronger negative obstruction on this subclass by itself;
so after [[five-qubit-stabilizer-cut-rank-satisfies-fsep.md]], the live gap is now exactly to find a stronger obstruction to ordinary hidden-vertex graph-cut representability than the current F_{\mathrm{sep}} test, or else prove ordinary hidden-vertex representability for a wider stabilizer subclass.

Dependencies¶

[[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]]
[[five-qubit-stabilizer-cut-rank-satisfies-fsep.md]]
[[four-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]]

Conflicts/Gaps¶

This node collapses generalized Boolean network representability back to the original hidden-vertex graph-cut question only for nontrivial stabilizer cut-rank functions. It does not decide that underlying ordinary graph-cut representability problem.
The result is Boolean-domain specific. It does not address whether non-Boolean domains, nonterminal constructions, or non-network algebraic representations could still be useful elsewhere.
Even a positive ordinary hidden-vertex graph-cut theorem would still not by itself produce routing-style CD(T_n,G) semantics on the physical qubit set.
The current universal necessary condition on disk is still F_{\mathrm{sep}}, and [[five-qubit-stabilizer-cut-rank-satisfies-fsep.md]] shows that it does not separate any 5-qubit stabilizer example.

Sources¶

10.1007/s10878-017-0136-y
10.1109/TIT.2009.2030492
10.48550/arXiv.2109.14599