Skip to content

2D Local Clifford Syndrome Space-Depth Tradeoff

Claim/Theorem

Delfosse, Beverland, and Tremblay prove that for any family of \(2\)D local Clifford syndrome-extraction circuits \(C_i\) for a family of local-expander quantum LDPC codes with code length \(n_i\to\infty\), supported on square patches with a total of \(N_i\) qubits,

\[ \operatorname{depth}(C_i)\;\ge\;\Omega\!\left(\frac{n_i}{\sqrt{N_i}}\right). \]

In particular, when \(N_i=\Theta(n_i)\) one obtains the desired static-grid lower bound

\[ \operatorname{depth}(C_i)\;=\;\Omega(\sqrt{n_i}), \]

and any bounded-depth \(2\)D implementation must instead use \(N_i=\Omega(n_i^2)\) total qubits.

Dependencies

  • [[expansion-cut-to-syndrome-depth.md]]
  • [[tanner-to-contracted-expansion-transfer.md]]

Conflicts/Gaps

  • The theorem is for \(2\)D local Clifford syndrome-extraction circuits with local preparations, local Pauli measurements, and unrestricted classical communication. This model is strictly stronger than SWAP-only compilation, so it proves the minimal SWAP-only lower bound a fortiori, but it still does not cover arbitrary compilation maps in the full CD(T_n,\mathfrak G) conjecture.
  • The source theorem assumes a local-expander code family. To apply it to Conjecture 3 as stated, one needs [[tanner-to-contracted-expansion-transfer.md]] or another bridge from Tanner-graph expansion to the paper's hypothesis.
  • The result is specific to static \(2\)D locality. It does not rule out architectures with extra nonlocal resources, bilayers, or teleportation-assisted gadgets.

Sources

  • 10.48550/arXiv.2109.14599