Skip to content

SWAP-Only 2D Check-Layer Cut Barrier

Claim/Theorem

The minimal Conjecture-3 lower bound on a static near-square \(2\)D grid is now literature-backed rather than only a bespoke proof sketch. Let \(T_n\) be a bounded-degree Tanner family with constant expansion, and compile one full syndrome-extraction round onto a static near-square \(2\)D grid with \(N=\Theta(n)\) physical sites using only nearest-neighbor gates and SWAPs. Then the physical depth of the round is

\[ \Omega(n / \sqrt{N}) = \Omega(\sqrt{n}). \]

This follows because [[tanner-to-contracted-expansion-transfer.md]] converts Tanner-graph expansion into the local-expander hypothesis used by [[2d-local-clifford-syndrome-space-depth-tradeoff.md]], and a SWAP-only circuit is a special case of the stronger \(2\)D local Clifford syndrome-extraction model handled there. The older cross-cut derivation through [[expander-cut-to-crossing-matching.md]] and [[cross-cut-matching-service-bound.md]] remains a useful internal route toward the fuller congestion-dilation statement.

For code families that are also good in the sense \(k=\Theta(n)\) and \(d=\Theta(n)\), [[2d-syndrome-depth-from-code-parameters.md]] independently recovers the same Omega(sqrt(n)) barrier in a more model-general 2D-local setting.

Dependencies

  • [[tanner-to-contracted-expansion-transfer.md]]
  • [[2d-local-clifford-syndrome-space-depth-tradeoff.md]]
  • [[2d-syndrome-depth-from-code-parameters.md]]
  • [[expander-cut-to-crossing-matching.md]]
  • [[cross-cut-matching-service-bound.md]]
  • [[2d-grid-routing-tightness.md]]

Conflicts/Gaps

  • This no longer depends on the persistent-check-register model, but it still does not prove the full lower bound D_emu(T_n -> G) >= c * CD(T_n,G) for arbitrary compilers.
  • The direct source theorem already allows local measurements and unrestricted classical communication inside the syndrome-extraction circuit. What remains open is extending from that stabilizer-measurement model to more general compilation maps, dynamic hardware, teleportation-style gadgets, or non-Clifford emulation strategies.
  • The hypothesis is an expanding Tanner family in the small-set sense needed by [[tanner-to-contracted-expansion-transfer.md]]. If one wants a specific explicit QLDPC family, that expansion property must be checked for the chosen stabilizer presentation.
  • The alternative route through [[2d-syndrome-depth-from-code-parameters.md]] uses good-code parameters instead of Tanner expansion, so it applies only when the chosen family has sufficiently large \(k\) and \(d\).

Sources

  • 10.48550/arXiv.2109.14599
  • 10.48550/arXiv.2302.04317
  • 10.1016/j.comgeo.2022.101862