Skip to content

Stabilizer Cut Rank Is Not A Graph Cut Function

Claim/Theorem

Exact guest-graph packaging of intrinsic cut rank can fail even for a four-qubit stabilizer space.

Let

\[ \mathcal S=\operatorname{span}\{Z_1Z_2Z_3Z_4\} \]

on qubit set \(Q=\{1,2,3,4\}\). Then for every nonempty proper subset \(L\subset Q\),

\[ \chi_L(\mathcal S)=1. \]

Indeed, the only nonzero stabilizer has support on all four qubits, so for every proper nontrivial cut one has \(\mathcal S_L=\mathcal S_{L^c}=\{0\}\) and therefore

\[ \chi_L(\mathcal S)=\dim\mathcal S=1. \]

Now suppose there were a nonnegative weighted graph \(T\) on the same vertex set \(Q\) whose cut function matched intrinsic cut rank:

\[ w(\delta_T(L))=\chi_L(\mathcal S)=1 \qquad \text{for all }\varnothing\neq L\subsetneq Q. \]

Write \(d_i=w(\delta_T(\{i\}))\) for the weighted degree of vertex \(i\). Singleton cuts force

\[ d_1=d_2=d_3=d_4=1. \]

For any pair \(\{i,j\}\), the graph cut identity gives

\[ w(\delta_T(\{i,j\}))=d_i+d_j-2w_{ij}. \]

Since every pair cut also has value 1, we obtain

\[ 1=1+1-2w_{ij}, \qquad\text{hence}\qquad w_{ij}=\frac{1}{2} \]

for every \(i\neq j\). But then each weighted degree is

\[ d_i=\sum_{j\neq i}w_{ij}=\frac{3}{2}, \]

contradicting \(d_i=1\).

Therefore \(\chi_L(\mathcal S)\) need not be the cut function of any weighted graph on the qubit set. So the service theorem in [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]] cannot, in general, be packaged exactly by an ordinary guest graph whose edge cuts reproduce intrinsic cut rank on all hardware cuts.

The remaining packaging frontier must therefore use a richer object than a graph cut on the original qubit coordinates, such as a presentation-dependent hypergraph, an auxiliary-vertex construction, or a directly submodular demand functional.

Dependencies

  • [[cross-cut-stabilizer-rank.md]]
  • [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]]
  • [[swap-only-compiler-extraction-reduces-cd-to-stabilizer-cut-rank.md]]

Conflicts/Gaps

  • This rules out only exact representation by a weighted graph on the original qubit set.
  • It does not rule out approximate graph representations, graphs with auxiliary vertices, hypergraph cut models, or directly submodular CD objects.
  • The example is small and nonexpanding; it isolates the representation-theoretic obstruction, not the asymptotic lower bound for Conjecture 3.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.48550/arXiv.0805.2199