Skip to content

2D Local Syndrome Tradeoff Tightness

Claim/Theorem

The same 2021 obstruction paper also gives matching achievability evidence within the same circuit model. For bounded-degree CSS codes, there exist \(2\)D local Clifford syndrome-extraction circuits with \(O(n^2)\) ancilla qubits and bounded depth. For hypergraph-product codes built from proportional-length classical LDPC codes, there exist \(2\)D local Clifford syndrome-extraction circuits with \(O(n)\) ancilla qubits and depth \(O(\sqrt{n})\). Therefore the lower-bound scale of [[2d-local-clifford-syndrome-space-depth-tradeoff.md]] is tight up to constants at both the bounded-depth/quadratic-space corner and the linear-space/square-root-depth corner.

Dependencies

  • [[2d-local-clifford-syndrome-space-depth-tradeoff.md]]

Conflicts/Gaps

  • The positive constructions are not for every expanding Tanner family. The bounded-depth construction is for bounded-degree CSS codes, and the linear-space \(O(\sqrt{n})\) construction is for hypergraph-product codes.
  • Tightness is established inside the source paper's \(2\)D local Clifford syndrome-extraction model, not for the full congestion-dilation functional or arbitrary coherent compilers.
  • These constructions show that extra ancillas can trade against depth, but only up to the source tradeoff. They do not provide a way around the \Omega(n/\sqrt{N}) law itself.

Sources

  • 10.48550/arXiv.2109.14599