Skip to content

Large k-Connected Set Gives Balanced Cut Rank

Claim/Theorem

Let \(C\) be a binary linear code on coordinate set \(E\), and let \(Z\subseteq E\) be a \(k\)-connected set in the sense that for every \(A\subseteq E\),

\[ \lambda_C(A)\ge \min\{|A\cap Z|,\ |Z-A|,\ k-1\}. \]

Then for any cut \(L\subseteq E\) that is \(\varepsilon\)-balanced on \(Z\), meaning

\[ \varepsilon |Z| \;\le\; |L\cap Z| \;\le\; (1-\varepsilon)|Z| \]

for some \(0<\varepsilon\le 1/2\), one has

\[ \lambda_C(L)\ge \min\{\varepsilon |Z|,\ k-1\}. \]

Equivalently, for a stabilizer space \(\mathcal S\) represented by a full-row-rank matrix with kernel code \(C\),

\[ \chi_L(\mathcal S)\ge \min\{\varepsilon |Z|,\ k-1\}. \]

Therefore, if the relevant parity-check matroid contains a \(k\)-connected set with

\[ |Z|=\Theta(n), \qquad k=\Theta(n), \]

then every cut that is balanced on \(Z\) already has

\[ \chi_L(\mathcal S)=\Omega(n). \]

Combining this with [[stabilizer-cut-rank-functional.md]] yields

\[ \operatorname{depth}(C)\ge \Omega\!\left(\frac{n}{|\partial L|}\right) \]

for any hardware family whose bottleneck cut is balanced on \(Z\).

So a linear-size, linearly connected set in the parity-check matroid is already sufficient to recover the desired cut-based lower bound.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[stabilizer-cut-rank-functional.md]]
  • [[tangle-breadth-gives-k-connected-set.md]]

Conflicts/Gaps

  • This is a reduction, not a source theorem about Quantum Tanner codes.
  • It requires cuts that are balanced on the highly connected set \(Z\), not merely balanced on the full hardware vertex set.
  • The missing step is now isolated very sharply: prove the existence of a linear-size, linearly connected set in the relevant parity-check matroid, or prove that hardware-balanced cuts must also be balanced on such a set.

Sources

  • 10.37236/12467
  • 10.48550/arXiv.2109.14599
  • 10.48550/arXiv.0805.2199