Separator Profile Bounds Code Distance¶
Claim/Theorem¶
Baspin and Krishna prove that if a family of quantum LDPC codes has associated connectivity graphs \(G_n\) with separation profiles \(s_n\), then the code distance obeys
\[
d_n\;=\;O(s_n(n)).
\]
In particular, if every induced subgraph has separator size at most \(O(r^c)\) for some constant \(0\le c\le 1\), then
\[
d_n\;=\;O(n^c).
\]
Thus any quantum LDPC family with superpolynomially good distance behavior must have connectivity graphs with nearly linear separators somewhere; low-separator connectivity is itself an obstruction.
Dependencies¶
- None.
Conflicts/Gaps¶
- The theorem is about a static connectivity-graph representation of a code, not about the depth of a syndrome-extraction circuit compiled onto time-dependent hardware.
- The connectivity graph representation depends on the chosen generating set. The paper shows this still captures important limitations, but it is not a canonical graph invariant of the code.
- This node is most useful as separator-based evidence for the full Conjecture-3 program, not as a standalone proof of the desired depth lower bound.
Sources¶
10.22331/q-2022-05-13-71110.48550/arXiv.2106.00765