Skip to content

Parallel Extension Of Binary Circuit Gives Threshold-Lift Cut Rank

Claim/Theorem

Let M be a binary matroid on a ground set E=P\sqcup Q, where P and Q are both nonempty. Assume:

  • P is a parallel class of M;
  • if p is any representative of that parallel class in the simplification \operatorname{si}(M), then Q\cup\{p\} is a circuit of \operatorname{si}(M).

Write

\[ m:=|P|, \qquad s:=|Q|. \]

For a cut L\subseteq E, set

\[ p_L:=|L\cap P|, \qquad q_L:=|L\cap Q|. \]

Then the connectivity function of M depends only on (p_L,q_L) and is given by

\[ \lambda_M(L) = \mathbf 1[p_L\ge 1,\ q_L<s] + \mathbf 1[q_L\ge 1,\ p_L<m]. \]

Equivalently,

\[ \lambda_M(L) = \mathbf 1[p_L\ge 1] + \mathbf 1[q_L\ge 1] - \mathbf 1[p_L=m]\mathbf 1[q_L\ge 1] - \mathbf 1[p_L\ge 1]\mathbf 1[q_L=s]. \]

Hence for any full-row-rank binary stabilizer matrix H whose column matroid is M, the stabilizer cut-rank function satisfies

\[ \chi_L(\mathcal S_H)=\lambda_M(L) \]

and is ordinarily hidden-vertex graph-cut representable by the same four-hidden-bit quadratic submodular energy from [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]].

Conversely, every family H_{m,s} from [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]] has this matroid structure. More strongly, every binary matroid satisfying the above hypotheses is isomorphic to one of those H_{m,s} families. So the threshold-lift pattern has a clean presentation-invariant characterization: it is exactly the class of binary matroids obtained by replacing one element of a circuit by a parallel class.

This is a derived structural theorem.

  1. By [[cross-cut-stabilizer-rank-rank-formula.md]], any stabilizer cut-rank function from a binary matrix H equals the connectivity function of its column matroid, so it is enough to compute \lambda_M.
  2. Because Q\cup\{p\} is a circuit in \operatorname{si}(M), the set Q is independent of rank s, and p\in\operatorname{cl}(Q) but p\notin\operatorname{cl}(R) for every proper subset R\subsetneq Q.
  3. Therefore a subset with parameters (p_L,q_L) has rank
\[ r(p_L,q_L)= \begin{cases} 0,& p_L=0,\ q_L=0,\\ 1,& p_L>0,\ q_L=0,\\ q_L+\mathbf 1[p_L>0],& 1\le q_L<s,\\ s,& q_L=s. \end{cases} \]

Indeed: - a nonempty subset of the parallel class P has rank 1; - any proper subset of Q is independent and does not span p; - the full set Q spans p because Q\cup\{p\} is a circuit. 4. Applying the same formula to the complement (m-p_L,s-q_L) gives

\[ \lambda_M(L)=r(p_L,q_L)+r(m-p_L,s-q_L)-s, \]

which simplifies exactly to the threshold-lift formula above. 5. The hidden-vertex realization now follows immediately from [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]], because the right-hand side depends only on the pair (m,s) and the counts (p_L,q_L). 6. For the converse structural characterization, choose any q_1\in Q. Since Q\cup\{p\} is a circuit, the set

\[ B:=\{p\}\cup (Q\setminus\{q_1\}) \]

is independent of size s, hence a basis of the represented vector space. In coordinates with respect to B,

  • p=e_1,
  • the s-1 elements of Q\setminus\{q_1\} become e_2,\dots,e_s,
  • the remaining element q_1 becomes e_1+\cdots+e_s,

because in a binary circuit the unique dependence is the total sum of the circuit elements.

Thus every such matroid is representable in exactly the normal form used in [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]].

Consequences for the current frontier:

  • the threshold-lift realization is not tied to one chosen generator matrix; it is a presentation-invariant binary-matroid phenomenon;
  • the current positive result extends exactly to the structural class “parallel extension of a circuit,” not just one hand-picked H_{m,s} coordinate family;
  • this is a wider theorem in invariant form, but not yet a larger isomorphism class than the explicit family already on disk;
  • any genuinely new positive theorem must therefore move beyond circuit-plus-parallel-class structure, while any negative theorem must find a different witness outside this structural class.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[parallel-class-affine-basis-family-is-hidden-vertex-graph-cut-representable.md]]

Conflicts/Gaps

  • This node characterizes the present threshold-lift family invariantly, but it does not classify all hidden-vertex representable stabilizer cut-rank functions.
  • The theorem is derived from basic binary-matroid circuit properties plus the explicit hidden-vertex construction already on disk; it is not stated verbatim in the cited papers.
  • Even this invariant structural theorem remains at the level of auxiliary-variable graph-cut expressibility and does not yet yield routing-style CD(T_n,G) semantics on the physical qubit set.

Sources

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