Parallel-Class Affine-Basis Family Is Hidden-Vertex Graph-Cut Representable¶

Claim/Theorem¶

Fix integers m>=1 and s>=2. Let H_{m,s} be the binary matrix whose columns are

m copies of e_1, indexed by a set P,
the s columns on a set Q, namely e_2,\dots,e_s together with

\[ u:=e_1+e_2+\cdots+e_s. \]

Let \mathcal S_{m,s} be the row space of H_{m,s}. For a cut L, write

\[ p:=|L\cap P|, \qquad q:=|L\cap Q|. \]

Then the intrinsic cut-rank function of \mathcal S_{m,s} depends only on (p,q) and is given by

\[ \chi_L(\mathcal S_{m,s}) = \mathbf 1[p\ge 1] + \mathbf 1[q\ge 1] - \mathbf 1[p=m]\mathbf 1[q\ge 1] - \mathbf 1[p\ge 1]\mathbf 1[q=s]. \]

Equivalently,

\[ \chi_L(\mathcal S_{m,s}) = \mathbf 1[p\ge 1,\ q<s] + \mathbf 1[q\ge 1,\ p<m]. \]

Moreover this whole family is expressible by binary submodular functions with auxiliary variables. Specifically, for x\in\{0,1\}^{m+s} and hidden bits (a,b,c,d)\in\{0,1\}^4,

\[ \chi_{L_x}(\mathcal S_{m,s}) = \min_{a,b,c,d} E_{m,s}(x,a,b,c,d), \]

where

\[ E_{m,s}(x,a,b,c,d) := a+b-ad-cb + \sum_{i\in P}\bigl(x_i(1-a)+(1-x_i)c\bigr) + \sum_{j\in Q}\bigl(x_j(1-b)+(1-x_j)d\bigr). \]

Every quadratic coefficient of E_{m,s} is nonpositive, so E_{m,s} is a binary submodular polynomial. Hence every \chi_{L_x}(\mathcal S_{m,s}) is ordinarily hidden-vertex graph-cut representable.

This is a derived explicit theorem. It contains [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]] as the special case (m,s)=(3,3).

By [[cross-cut-stabilizer-rank-rank-formula.md]], \chi_L(\mathcal S_{m,s}) is the rank-connectivity function \lambda_{H_{m,s}}(L)=r(L)+r(E\setminus L)-r(E).
The total rank is r(E)=s, because the columns e_1,e_2,\dots,e_s all lie in the span of H_{m,s}.
For a subset with parameters (p,q), the restricted rank is

\[ r(p,q)= \begin{cases} 0,& p=0,\ q=0,\\ 1,& p>0,\ q=0,\\ q+\mathbf 1[p>0],& 1\le q<s,\\ s,& q=s. \end{cases} \]

Indeed:
- the P-columns are a parallel class of rank 1;
- any proper subset of Q is independent, because removing at least one of e_2,\dots,e_s,u prevents e_1 from lying in its span;
- the full set Q has rank s, since u together with e_2,\dots,e_s spans e_1.
Therefore

\[ \lambda_{H_{m,s}}(L)=r(p,q)+r(m-p,s-q)-s, \]

and the case split above gives exactly

\[ \lambda_{H_{m,s}}(L) = \mathbf 1[p\ge 1,\ q<s] + \mathbf 1[q\ge 1,\ p<m]. \]
Now define threshold bits

\[ a_P:=\mathbf 1[p\ge 1],\qquad c_P:=\mathbf 1[p=m],\qquad b_Q:=\mathbf 1[q\ge 1],\qquad d_Q:=\mathbf 1[q=s]. \]

Then

\[ \chi_L(\mathcal S_{m,s})=a_P+b_Q-a_P d_Q-c_P b_Q. \]
The energy E_{m,s} realizes exactly these thresholds:
- minimizing over (a,c) on P produces \mathbf 1[p\ge 1,\ q<s],
- minimizing over (b,d) on Q produces \mathbf 1[q\ge 1,\ p<m].
More explicitly,

\[ E_{m,s} = \underbrace{a+p(1-a)+d(s-q-a)}_{G_{p,q}^{(m,s)}(a,d)} + \underbrace{b+q(1-b)+c(m-p-b)}_{H_{p,q}^{(m,s)}(b,c)}, \]

so the minimization separates. If q<s, then d=0 is optimal and \min_a G_{p,q}^{(m,s)}(a,0)=\min\{p,1\}=\mathbf 1[p\ge 1]; if q=s, then (a,d)=(1,1) gives value 0. Symmetrically, \min_{b,c} H_{p,q}^{(m,s)}(b,c)=\mathbf 1[q\ge 1,\ p<m].
Hence

\[ \min_{a,b,c,d} E_{m,s}(x,a,b,c,d) = \mathbf 1[p\ge 1,\ q<s] + \mathbf 1[q\ge 1,\ p<m] = \chi_{L_x}(\mathcal S_{m,s}), \]

proving the realization.

Consequences for the current frontier:

the explicit 6-qubit realization from [[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]] is not an isolated coincidence; it belongs to an infinite stabilizer/binary-matroid family;
this gives a genuine positive theorem beyond the modular-plus-fan cone, because the family contains the arity-6 member (m,s)=(3,3) already known to escape that cone via [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]];
any negative theorem must therefore exclude a larger class than the current fan-cone obstruction, while any positive theorem may try to characterize when stabilizer cut-rank reduces to this threshold-lift pattern.

Dependencies¶

[[cross-cut-stabilizer-rank-rank-formula.md]]
[[six-qubit-witness-is-hidden-vertex-graph-cut-representable.md]]
[[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]]

Conflicts/Gaps¶

This node proves a concrete infinite family, not a characterization of all hidden-vertex representable stabilizer cut-rank functions.
The theorem is derived by explicit rank computation and explicit energy construction, not stated verbatim in the cited papers.
The result still lives at the level of auxiliary-variable graph-cut expressibility and does not yet produce routing-style CD(T_n,G) semantics on the physical qubit set.

Sources¶

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