Skip to content

Wolf Parameter Bound Is Insufficient For CSS QLDPC Constituents

Claim/Theorem

For CSS qLDPC constructions, Wolf's trellis-width lower bound based on classical parameters cannot by itself yield a superconstant static-2D depth lower bound when applied to the constituent classical codes. Equivalently, after [[matroid-pathwidth-equals-code-trellis-width.md]], the same obstruction says that parameter-only lower bounds on the associated matroid pathwidth are asymptotically useless here.

Let \(C_0=\ker H_0\) and \(C_1=\ker H_1\) be the constituent classical codes of a CSS qLDPC family with LDPC check weight bounded by a constant \(w\). By [[qldpc-css-constituent-codes-not-good.md]],

\[ d(C_0),\,d(C_1)\;\le\;w=O(1). \]

Wolf's lower bound for a classical [n,k,d] code gives only

\[ \operatorname{tw}(C_i) \;\in\; \Omega\!\left(\frac{k_i(d(C_i)-1)}{n}\right) \;=\; \Omega(1) \]

when \(k_i=O(n)\) and \(d(C_i)=O(1)\).

Feeding this into [[hardware-cutwidth-to-syndrome-depth.md]] on a near-square static 2D grid with cutwidth Theta(sqrt(N)) yields at best

\[ \operatorname{depth}(C) \;\in\; \Omega\!\left(\frac{1}{\sqrt N}\right), \]

which is asymptotically useless for proving a nontrivial lower bound.

So the cutwidth or pathwidth route is not wrong, but the specific Wolf-parameter instantiation of it is too weak for CSS qLDPC constituent codes. To make that route decisive, one would need a lower bound on trellis-width or matroid pathwidth coming from some structure other than classical distance, such as expansion, local testability, or a new matroid-connectivity argument.

Dependencies

  • [[qldpc-css-constituent-codes-not-good.md]]
  • [[matroid-pathwidth-equals-code-trellis-width.md]]
  • [[hardware-cutwidth-to-syndrome-depth.md]]

Conflicts/Gaps

  • This node only says that the standard parameter lower bound is too weak. It does not prove that the actual trellis-width of the constituent codes is small.
  • Therefore it does not rule out a future sharp cutwidth proof for Quantum Tanner families; it only shows that such a proof would need new structural input beyond the classical distance of \(C_0\) or \(C_1\).
  • The statement is about the constituent classical-code route and does not affect the already-established expander-based and low-dimensional-overhead lower bounds elsewhere on the graph.

Sources

  • 10.48550/arXiv.2202.13641
  • 10.48550/arXiv.0805.2199