Skip to content

Quantum Tanner Theorem 17 Static 2D Barrier

Claim/Theorem

Fix a quantum Tanner family built from local component codes \(C_A,C_B\) satisfying the hypotheses of Theorem 17 of Leverrier and Zemor, with \(\Delta>4\) large enough. Consider the specific local-generator stabilizer presentation obtained by choosing connected bases for the local tensor codes as in [[quantum-tanner-theorem17-parity-expander.md]]. Then any static near-square 2D syndrome-extraction circuit that measures this chosen presentation on N physical qubits obeys

\[ \operatorname{depth}(C)\;=\;\Omega\!\left(\frac{n}{\sqrt{N}}\right). \]

In particular, in the linear-space regime N=Theta(n),

\[ \operatorname{depth}(C)\;=\;\Omega(\sqrt{n}). \]

Because SWAP-only compilation is a special case of the stronger local-Clifford stabilizer-measurement model, the same asymptotic lower bound holds a fortiori for SWAP-only compilation onto a static near-square 2D grid.

The reason is that [[quantum-tanner-theorem17-parity-expander.md]] gives a local-expander Tanner presentation for each parity subcircuit of this chosen basis. Applying [[expansion-cut-to-syndrome-depth.md]] to one such parity extraction and then using [[2d-grid-bisection-width.md]] for a balanced cut of the static near-square grid gives the stated Omega(n/sqrt(N)) lower bound. A full round that literally measures this chosen presentation must include that parity extraction, so the same lower bound applies to that round.

Thus the explicit-family anchor has reached a clean chosen-presentation lower bound. Extending it from this explicit local-generator basis to every syndrome basis of the same code is now separated out as the intrinsic cut-rank problem captured by [[cross-cut-stabilizer-rank.md]] and [[stabilizer-cut-rank-functional.md]].

Dependencies

  • [[quantum-tanner-theorem17-parity-expander.md]]
  • [[expansion-cut-to-syndrome-depth.md]]
  • [[2d-grid-bisection-width.md]]

Conflicts/Gaps

  • This is still conditional on the component-code hypotheses of Theorem 17. The paper's Theorem 18 supplies one random existence mechanism, but the current graph still lacks an explicit deterministic component-code family satisfying those hypotheses.
  • The claim is presentation-specific: it applies to the chosen local-generator basis isolated in [[quantum-tanner-theorem17-parity-expander.md]], not yet to every generating set of the same stabilizer space.
  • For the bare static-2D Omega(sqrt(n)) target, a stronger basis-independent theorem is already available via [[quantum-tanner-good-family-presentation-invariant-2d-barrier.md]]. The present node remains useful because it is structurally closer to the conjectured CD(T_n,\mathfrak G) route.
  • The lower bound is proved in the stronger 2D local-Clifford stabilizer-measurement model. It therefore implies the SWAP-only target, but it still does not settle the full compiler-class CD(T_n,\mathfrak G) conjecture.
  • The statement is about static near-square 2D hardware. It does not rule out resource-augmented escapes such as thin planar nonlocal wiring, bilayers with LOCC assistance, teleportation paths, or hierarchical memories.

Sources

  • 10.48550/arXiv.2202.13641
  • 10.48550/arXiv.2109.14599