Good Codes Have Logarithmic Branchwidth

Claim/Theorem

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

\[ \sigma(C) \;:=\; \min_{(T,\omega)\in\mathcal Q(C)} \max_{e\in E(T)} \lambda_C(J(e)) \]

denote the code branchwidth in the sense of minimal tree realizations, where \(J(e)\) is the coordinate subset displayed by the tree edge \(e\) and

\[ \lambda_C(L)=\dim(C|_L)+\dim(C|_{L^c})-\dim(C). \]

Then

\[ \sigma(C) \;\in\; \Omega\!\left( \frac{k(d-1)}{n\log n} \right). \]

More explicitly, combining Kashyap's treewidth lower bound with the branchwidth-treewidth comparison of Forney, Hu, Kschischang, and Koetter gives

\[ \sigma(C) \;\ge\; \frac{k(d-1)}{2\,n\,(3+2\log_2(n-1))}. \]

Equivalently, every cubic tree decomposition of the coordinate set of \(C\) has some displayed cut \(L\) with

\[ \lambda_C(L)\;\ge\;\frac{k(d-1)}{2\,n\,(3+2\log_2(n-1))}. \]

Using [[cross-cut-stabilizer-rank-rank-formula.md]], the same statement can be read as an intrinsic stabilizer claim: for any stabilizer space \(\mathcal S\) represented by a full-row-rank matrix with kernel \(C\), every branch decomposition has an edge-displayed cut with

\[ \chi_L(\mathcal S)\;\in\;\Omega\!\left(\frac{k(d-1)}{n\log n}\right). \]

So good codes do not just have some large cut as in [[good-codes-have-some-linear-cut-rank.md]]; they already force logarithmically large intrinsic connectivity in every tree decomposition of the coordinate set.

Dependencies

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

Conflicts/Gaps

• This is still weaker than the balanced-cut statement needed for Conjecture 3. A branch decomposition edge of width Omega(n/log n) need not correspond to a balanced coordinate partition or to a cut aligned with a hardware separator.
• The direct-sum obstruction in [[good-code-parameters-do-not-imply-cut-rank.md]] shows that even very good code parameters do not force linear balanced-cut connectivity, so branchwidth alone does not close the frontier.
• Turning this intrinsic branchwidth lower bound into a circuit-depth theorem still needs an additional bridge: either a theorem relating hardware-limited circuits to low-width graphical realizations, or a structural result showing that the relevant Quantum Tanner stabilizer spaces have large balanced-cut connectivity rather than merely large branchwidth.

Sources

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