Skip to content

Connected Hidden-Vertex Realizability Still Fails Terminal Routing Semantics

Claim/Theorem

Keep the notation of [[five-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]], [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]], [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]], and [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]].

Exact hidden-vertex graph-cut realizability is already too weak to recover routing-style terminal semantics, even on a connected binary-matroid or stabilizer example.

More precisely, consider the 5-qubit stabilizer space from [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]], represented by

\[ H= \begin{bmatrix} 1&0&1&0&1\\ 0&1&1&0&0\\ 0&0&0&1&1 \end{bmatrix}, \]

with generators

\[ Z_1Z_3Z_5,\qquad Z_2Z_3,\qquad Z_4Z_5. \]

Let

\[ f_{\mathcal S}(x):=\chi_{L_x}(\mathcal S). \]

Then:

  1. By [[five-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]], every 5-qubit stabilizer cut-rank function is expressible by binary submodular functions with auxiliary variables. In particular, this connected example is ordinarily hidden-vertex graph-cut representable.

  2. The underlying binary matroid is connected. Indeed, the column matroid of H has circuits

    \[ \{1,2,3\} \qquad\text{and}\qquad \{1,4,5\}, \]

    which intersect in element 1, so every element lies in one circuit-connected component.

  3. Nevertheless, [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]] proves that the same function f_{\mathcal S} is not the cut-capacity function of any undirected hypergraph with nonnegative terminal capacities.

  4. Therefore f_{\mathcal S} admits an exact auxiliary-variable min-cut realization while failing every exact terminal nonnegative-hypergraph semantics.

  5. Since terminal graph cuts, packet-demand graphs, and path-routing cut capacities on the physical qubit set are all special cases of terminal nonnegative-hypergraph cut functions, none of those routing-style semantics can represent this same connected example exactly.

Therefore the Route-D semantic gap is now explicit:

exact hidden-vertex realizability on a connected binary or stabilizer instance does not imply any routing-style classical semantics on the physical terminal set.

Equivalently, auxiliary-variable expressibility is not yet a usable compiler semantics. It is only an algebraic representability statement.

Dependencies

  • [[five-qubit-stabilizer-cut-rank-is-hidden-vertex-graph-cut-representable.md]]
  • [[simple-binary-connectivity-violates-nonnegative-hypergraph-cut-condition.md]]
  • [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]]
  • [[submodular-cut-congestion-lower-bounds-swap-only-compiler-depth.md]]

Conflicts/Gaps

  • This theorem separates hidden-vertex realizability from exact terminal routing semantics. It does not rule out all auxiliary constructions with hidden vertices, signed capacities, or other nonterminal algebraic encodings.
  • The statement is witness-level, not yet a whole-family impossibility theorem on a substantial connected subclass.
  • It concerns exact terminal semantics. It does not yet settle whether some weaker approximate or nonterminal classical interpretation could still be useful for compiler lower bounds.

Sources

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