Six-Qubit Witness Is Hidden-Vertex Graph-Cut Representable

Claim/Theorem

Let f_{\mathcal S} be the 6-ary Boolean cut-rank function from [[six-qubit-witness-satisfies-direct-fsep.md]], equivalently from the stabilizer matrix

\[ H= \begin{pmatrix} 1&0&0&1&1&1\\ 0&1&0&0&0&1\\ 0&0&1&0&0&1 \end{pmatrix}. \]

Write P=\{1,4,5\} and Q=\{2,3,6\}, and for x\in\{0,1\}^6 set

\[ p(x):=\sum_{i\in P} x_i, \qquad q(x):=\sum_{j\in Q} x_j. \]

Then f_{\mathcal S} is expressible by binary submodular functions with auxiliary variables. More concretely, with hidden bits (a,b,c,d)\in\{0,1\}^4,

\[ f_{\mathcal S}(x) = \min_{a,b,c,d} E(x,a,b,c,d), \]

where

\[ E(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 in E is nonpositive, so E is a binary submodular polynomial on the visible and hidden variables. Hence f_{\mathcal S}\in\langle \Gamma_{\mathrm{sub},2}\rangle, equivalently f_{\mathcal S} is ordinarily hidden-vertex graph-cut representable.

This is a derived explicit realization theorem.

1. By [[six-qubit-witness-satisfies-direct-fsep.md]], one already has the grouped formula

   \[ f_{\mathcal S}(x) = \mathbf 1[p(x)\ge 1] + \mathbf 1[q(x)\ge 1] - \mathbf 1[p(x)\ge 1]\mathbf 1[q(x)=3] - \mathbf 1[p(x)=3]\mathbf 1[q(x)\ge 1]. \]

   Equivalently, if

   \[ a_P:=\mathbf 1[p(x)\ge 1],\qquad c_P:=\mathbf 1[p(x)=3],\qquad b_Q:=\mathbf 1[q(x)\ge 1],\qquad d_Q:=\mathbf 1[q(x)=3], \]

   then

   \[ f_{\mathcal S}(x)=a_P+b_Q-a_P d_Q-c_P b_Q. \]

2. The energy E realizes exactly those threshold bits through pairwise penalties:

   • a is the OR-threshold on P,
   • c is the all-ones threshold on P when b=1,
   • b is the OR-threshold on Q,
   • d is the all-ones threshold on Q when a=1.

3. Grouping terms by the two triples gives

   \[ E(x,a,b,c,d) = \underbrace{a+p(x)(1-a)+d(3-q(x)-a)}_{G_{p,q}(a,d)} + \underbrace{b+q(x)(1-b)+c(3-p(x)-b)}_{H_{p,q}(b,c)}. \]

   So minimization splits into two independent 2-bit problems:

   \[ \min_{a,d} G_{p,q}(a,d) + \min_{b,c} H_{p,q}(b,c). \]

4. For fixed p,q\in\{0,1,2,3\}, direct inspection gives

   \[ \min_{a,d} G_{p,q}(a,d)=\mathbf 1[p\ge 1\ \text{and}\ q<3], \]

   because

   • if q<3, then d=0 is optimal and the remaining minimum is \min\{p,1\}=\mathbf 1[p\ge 1],
   • if q=3, then a=1,d=1 gives value 0, and no negative value is possible.

5. By symmetry,

   \[ \min_{b,c} H_{p,q}(b,c)=\mathbf 1[q\ge 1\ \text{and}\ p<3]. \]

6. Therefore

   \[ \min_{a,b,c,d}E(x,a,b,c,d) = \mathbf 1[p\ge 1,\ q<3] + \mathbf 1[q\ge 1,\ p<3]. \]

   This equals

   \[ \mathbf 1[p\ge 1]+\mathbf 1[q\ge 1]-\mathbf 1[p\ge 1]\mathbf 1[q=3]-\mathbf 1[p=3]\mathbf 1[q\ge 1] = f_{\mathcal S}(x), \]

   which proves the realization.

Consequences for the current frontier:

• the 6-qubit witness from [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]] is not a counterexample to ordinary hidden-vertex graph-cut representability;
• the fan-cone obstruction and the direct F_{\mathrm{sep}} pass from [[six-qubit-witness-satisfies-direct-fsep.md]] are now reconciled by an explicit four-hidden-bit realization;
• any negative theorem must therefore look beyond this witness, while any positive theorem beyond the fan cone can use this node as the first genuine arity-6 realization template.

Dependencies

• [[six-qubit-witness-satisfies-direct-fsep.md]]
• [[six-qubit-stabilizer-cut-rank-escapes-modular-plus-fan-cone.md]]
• [[cross-cut-stabilizer-rank-rank-formula.md]]

Conflicts/Gaps

• This node is witness-specific. It does not prove that all 6-qubit stabilizer cut-rank functions are hidden-vertex graph-cut representable.
• The realization is derived by explicit construction, not quoted verbatim from the cited papers.
• Hidden-vertex representability still does not by itself yield a routing-style CD(T_n,G) interpretation on the physical qubit set.

Sources

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