Skip to content

Cut Rank Is Interface State Dimension

Claim/Theorem

Let \(C\) be a linear code on coordinate set \(I\), and let a tree edge \(e\) in a tree decomposition of \(I\) induce the partition

\[ I = J \sqcup J^c. \]

Then in the minimal tree realization of \(C\) extending that decomposition, the state-space dimension on the edge \(e\) is exactly

\[ \lambda_C(J) \;:=\; \dim(C|_J)+\dim(C|_{J^c})-\dim(C). \]

Equivalently, for a stabilizer space \(\mathcal S\) represented by a full-row-rank matrix \(H\) with kernel \(C=\ker H\), the interface dimension on that edge is exactly

\[ \chi_J(\mathcal S). \]

So intrinsic cut rank is not just an abstract connectivity number. It is the exact number of binary state bits needed to glue the left and right parts of the code across that cut in an optimal tree realization.

This makes the current frontier more precise: proving linear balanced-cut rank is the same as proving that every hardware-relevant balanced separator cut carries a linear-size interface state.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]

Conflicts/Gaps

  • This theorem is exact for classical tree realizations of the code \(C=\ker H\), but it does not automatically identify the interface complexity of an arbitrary quantum compilation or stabilizer-measurement circuit.
  • It still does not show how tester-side approximate product decompositions, such as [[ltc-sparse-cut-product-decomposition.md]], translate into lower bounds on exact interface dimension.
  • The theorem is most useful as a bridge concept: it turns the open problem into a question about forcing large state spaces across hardware-aligned cuts.

Sources

  • 10.48550/arXiv.0711.1383
  • 10.48550/arXiv.0805.2199