Skip to content

Code Realization VC-Treewidth Bound

Claim/Theorem

Let \(C\) be an [n,k,d] linear code over a finite field, and let \(\kappa(C;G)\) denote the minimum local constraint complexity of any graphical realization of \(C\) on a connected graph \(G\) in the sense of Kashyap. Then

\[ \kappa(C;G)\;\ge\;\frac{\kappa_{\mathrm{tree}}(C)}{\kappa_{\mathrm{vc\text{-}tree}}(G)}, \]

and Kashyap's Proposition 6.8 gives

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

Therefore

\[ \kappa(C;G) \;\ge\; \frac{k(d-1)}{\kappa_{\mathrm{vc\text{-}tree}}(G)\,n\,(3+2\log_2(n-1))}. \]

Equivalently, if a code family has bounded-complexity graphical realizations on graphs whose vc-treewidth is uniformly bounded by a constant, then that family cannot be asymptotically good. More generally, good codes can have low-complexity realizations only on graphs with vc-treewidth at least on the order of n/log n.

This does not yet solve Conjecture 3, but it supplies a rigorous low-treewidth obstruction that is structurally close to the desired hardware-constrained lower bound.

Dependencies

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

Conflicts/Gaps

  • This theorem is about graphical realizations of classical linear codes with bounded local constraint complexity, not directly about syndrome-extraction circuits or stabilizer-measurement depth.
  • To use it for Conjecture 3, one still needs a theorem converting a bounded-depth local compilation or syndrome-extraction circuit into a bounded-complexity graphical realization on an appropriate space-time graph.
  • The lower bound has a logarithmic loss through Kashyap's treewidth bound, so even after a circuit-to-realization reduction it may be weaker than the sharp Omega(n/\sqrt{N}) theorems already on the graph.

Sources

  • 10.48550/arXiv.0805.2199