Skip to content

Quantum Tanner Random-Model Static 2D Barrier

Claim/Theorem

For the existence-style random local-code model of Leverrier and Zemor's Theorem 18, the current graph yields an existence-style static-2D lower bound for the specific chosen local-generator presentation furnished by the current explicit-family route.

This is now an immediate corollary of [[quantum-tanner-theorem17-static-2d-barrier.md]]. Theorem 18 states that with nonzero probability the random component codes satisfy the hypotheses of Theorem 17. On that event, the deterministic conditional node [[quantum-tanner-theorem17-static-2d-barrier.md]] applies to the chosen local-generator presentation and gives

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

for any static near-square 2D implementation on N qubits, and in the linear-space regime N=\Theta(n) one obtains

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

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

So the random-model statement remains valid, but it is no longer the sharpest theorem node on the graph. Its role is now to package the paper's probabilistic existence mechanism as a corollary of the stronger deterministic conditional theorem.

Dependencies

  • [[quantum-tanner-theorem17-static-2d-barrier.md]]

Conflicts/Gaps

  • The statement is still existence-style because Theorem 18 is probabilistic. The stronger deterministic conditional content now lives in [[quantum-tanner-theorem17-static-2d-barrier.md]].
  • Like its parent node, this statement is about the chosen local-generator presentation, not yet every syndrome basis of the same code.
  • The node still lives inside the stabilizer-measurement / local-Clifford framework. It does not yet establish the full compiler-independent congestion-dilation conjecture.
  • The graph still lacks an explicit deterministic component-code family known to satisfy Theorem 17.

Sources

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