Skip to content

Four-Qubit Stabilizer Cut Rank Is Hidden-Vertex Graph-Cut Representable

Claim/Theorem

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

\[ f_{\mathcal S}(x_1,x_2,x_3,x_4):=\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.

This is a derived finite theorem from two ingredients.

  1. [[cross-cut-stabilizer-rank-rank-formula.md]] identifies \chi_L(\mathcal S) with binary matroid connectivity, hence f_{\mathcal S} is a normalized symmetric 4-ary submodular Boolean cost function.
  2. Živný, Cohen, and Jeavons prove in Theorem 22 (p. 10) that a 4-ary submodular Boolean cost function is expressible by binary submodular functions if and only if it satisfies condition Sep; equivalently, by Theorem 16 (p. 9), if and only if it has multimorphism F_{\mathrm{sep}}.

An exhaustive computation over all 67 subspaces of GF(2)^4 gives:

  • these produce 18 distinct connectivity functions L\mapsto \chi_L(\mathcal S) on the 16 subsets of Q;
  • every one of those 18 functions satisfies all three Sep inequalities from Theorem 22;
  • therefore every 4-qubit stabilizer cut-rank function lies in \langle \Gamma_{\mathrm{sub},2}\rangle.

Consequently, there is no 4-qubit stabilizer-space counterexample to hidden-vertex graph-cut representability. Any negative result against auxiliary-vertex graph-cut models inside the binary-matroid or stabilizer subclass must start at arity at least 5.

This also clarifies the scope of [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]]: that node rules out ordinary terminal graph edge cuts, but not graph-cut realizations with hidden vertices. Its explicit 4-qubit example still satisfies Sep, in fact with equality in all three partitions.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[stabilizer-cut-rank-is-not-a-graph-cut-function.md]]

Conflicts/Gaps

  • This is an exact theorem only for arity 4. It leaves open whether some 5-qubit stabilizer cut-rank function fails hidden-vertex graph-cut expressibility.
  • The argument is existential rather than constructive: it uses Živný-Cohen-Jeavons's characterization and a finite exhaustive check, not an explicit gadget library for every 4-qubit stabilizer space.
  • Even when hidden-vertex graph-cut expressibility holds, it does not yet produce the desired routing-style CD(T_n,G) semantics on the physical qubit set; the hidden vertices are algebraic auxiliary variables, not yet packet or path demands.
  • [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]] still shows that exact nonnegative hypergraph cut semantics already fail at 5 qubits, so the surviving auxiliary-vertex route is strictly narrower than ordinary terminal graph or hypergraph cut models.

Sources

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