Skip to content

Nonlocality Cost For Good QLDPC

Claim/Theorem

Baspin and Krishna quantify how much long-range connectivity is required to implement quantum LDPC codes that outperform geometrically local code tradeoffs. In 2D, a quantum LDPC code with distance scaling as \(d \propto n^{1/2+\epsilon}\) requires \(\Omega(n^{1/2+\epsilon})\) interactions of length \(\widetilde{\Omega}(n^\epsilon)\). More generally, a code with \(k\propto n\) and \(d\propto n^\alpha\) requires \(\widetilde{\Omega}(n)\) interactions of length \(\widetilde{\Omega}(n^{\alpha/2})\). This is direct quantitative evidence that genuinely good QLDPC behavior is expensive under strict 2D locality.

Dependencies

  • None.

Conflicts/Gaps

  • The theorem is about the long-range interactions required to implement a code family, not directly about the depth of a SWAP-only syndrome-extraction round.
  • It is a general nonlocality lower bound, not a statement about expander-style Tanner graphs in particular.
  • The result supports Conjecture 3 conceptually and quantitatively, but it does not by itself prove the Omega(sqrt(n)) round-depth theorem candidate already on the graph.

Sources

  • 10.1103/PhysRevLett.129.050505