Skip to content

Expansion Cut To Syndrome Depth

Claim/Theorem

Inside the local Clifford stabilizer-measurement model, local expansion converts directly into a cut lower bound on circuit depth. Combining [[contracted-expansion-to-cross-cut-stabilizers.md]] with [[stabilizer-measurement-cut-lower-bound.md]] gives:

if a subset \(L\) of circuit qubits contains \(\Theta(n)\) data qubits from a bounded-weight local-expander quantum LDPC code, then

\[ \operatorname{depth}(C)\;=\;\Omega\!\left(\frac{n}{|\partial L|}\right), \]

where \(\partial L\) is the edge boundary of \(L\) in the circuit connectivity graph. Equivalently, once a hardware cut carries only \(|\partial L|\) interactions per layer, a balanced cut of an expanding code forces depth at least linear in the logical cross-cut demand divided by that cut capacity.

Dependencies

  • [[stabilizer-measurement-cut-lower-bound.md]]
  • [[contracted-expansion-to-cross-cut-stabilizers.md]]

Conflicts/Gaps

  • This theorem is still about stabilizer-measurement circuits built from local Clifford operations. It is not yet a compiler-independent lower bound on CD(T_n,\mathfrak G).
  • The lower bound is only useful when one can exhibit a cut \(L\) that captures a constant fraction of data qubits while keeping \(|\partial L|\) small.
  • The node is deliberately stated in terms of edge boundary rather than a specific geometry. Additional hardware graph theorems are needed to specialize it to planar, minor-free, or other constrained architectures.

Sources

  • 10.48550/arXiv.2109.14599