Skip to content

Tanner To Contracted Expansion Transfer

Claim/Theorem

Let \(T\) be the Tanner graph of a stabilizer code with length \(n\) and \(r\) stabilizer generators, and let \(\bar T\) be its contracted Tanner graph on data qubits. Then for every \(\varepsilon\in[0,1]\),

\[ h_{\varepsilon'}(\bar T)\;\ge\;\frac{h_\varepsilon(T)}{\deg(T)}, \qquad \varepsilon'=\frac{n+r}{(1+\deg(T))\,n}\,\varepsilon. \]

Consequently, any bounded-degree Tanner family with constant small-set expansion yields a local-expander contracted Tanner family. This is exactly the hypothesis needed by the 2D syndrome-extraction lower bound of [[2d-local-clifford-syndrome-space-depth-tradeoff.md]].

Dependencies

  • None.

Conflicts/Gaps

  • The transfer requires actual expansion of the Tanner graph for the chosen stabilizer-generator set; good code parameters alone do not imply this hypothesis.
  • The conclusion is about the contracted Tanner graph of a fixed stabilizer presentation. If one changes generators or replaces stabilizer measurement by a different gadget graph, the expansion transfer must be re-checked.
  • This node bridges the conjecture's Tanner-expansion assumption to the source paper's local-expander hypothesis, but it does not itself impose any hardware or compilation constraint.

Sources

  • 10.48550/arXiv.2109.14599