Skip to content

Balanced Linear Cut-Rank From Trellis Width

Claim/Theorem

Every good linear code has not just some large cut-rank, but a large cut-rank across a balanced prefix cut.

Let \(C\) be an [n,k,d] linear code, and let

\[ h\;:=\;\left\lceil \frac{k(d-1)}{n}\right\rceil. \]

Then for every coordinate ordering \(\pi\), there exists a prefix cut \(L=P_i^\pi\) such that

\[ \lambda_C(L)\;\ge\;h, \qquad h\;\le\;|L|\;\le\;n-h. \]

Equivalently, for any stabilizer space \(\mathcal S\) with kernel code \(C=\ker H\), every ordering of the qubits has a balanced prefix cut with

\[ \chi_L(\mathcal S)\;\ge\;h. \]

In particular, for any asymptotically good family with \(k=\Theta(n)\) and \(d=\Theta(n)\), there exists a constant \(\varepsilon>0\) such that every ordering has a prefix cut satisfying

\[ \varepsilon n \;\le\; |L| \;\le\; (1-\varepsilon)n, \qquad \chi_L(\mathcal S)\;=\;\Omega(n). \]

Proof sketch:

  1. By the trellis-width lower bound used in [[good-codes-have-some-linear-cut-rank.md]], every ordering \(\pi\) has some prefix cut \(P_i^\pi\) with

    \[ \lambda_C(P_i^\pi)\;\ge\;h. \]

  2. Along any ordering, the prefix connectivity sequence changes by at most 1 at each step:

    \[ |\lambda_C(P_{i+1}^\pi)-\lambda_C(P_i^\pi)|\le 1, \]

    because adding one coordinate changes each projected rank by at most 1.

  3. Since \(\lambda_C(P_0^\pi)=\lambda_C(P_n^\pi)=0\), any prefix where the sequence reaches height at least \(h\) must lie at distance at least \(h\) from both endpoints. Hence the maximizing prefix satisfies

    \[ h\le i\le n-h. \]

    So linear trellis width automatically forces a balanced linear cut in every ordering.

Dependencies

  • [[good-codes-have-some-linear-cut-rank.md]]
  • [[cross-cut-stabilizer-rank-rank-formula.md]]

Conflicts/Gaps

  • This theorem removes “balancedness” as a missing issue for ordering-based cuts, but it still does not imply that an arbitrary hardware-balanced separator cut has large connectivity.
  • The direct-sum obstruction in [[good-code-parameters-do-not-imply-cut-rank.md]] remains valid: a code can have some balanced cuts with zero connectivity and other balanced cuts with linear connectivity.
  • Therefore the real remaining invariant gap is alignment with the small-capacity cuts forced by hardware geometry, not mere existence of a balanced linear cut.

Sources

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