Skip to content

2D Syndrome Depth From Code Parameters

Claim/Theorem

Baspin, Fawzi, and Shayeghi prove in their syndrome-extraction depth theorem (Theorem 24, specialized to D=2) that for any [n,k,d] stabilizer code, any 2D-local syndrome-extraction circuit on \(m\) qubits using arbitrary local operations and free classical computation must satisfy

\[ \Delta\;\in\;\Omega\!\left(\frac{k\sqrt{d}}{m}\right). \]

Therefore, for any good stabilizer family with \(k=\Theta(n)\) and \(d=\Theta(n)\) implemented with \(m=\Theta(n)\) physical qubits, one necessarily has

\[ \Delta\;=\;\Omega(\sqrt{n}). \]

This gives a second route to the minimal Conjecture-3 barrier that no longer uses Tanner expansion, at the cost of a weaker ancilla tradeoff when \(m\) is much larger than \(n\).

Dependencies

  • None.

Conflicts/Gaps

  • This theorem is 2D-specific. It does not directly cover more general hardware graph families without an analogue of the geometric argument.
  • The bound is weaker than [[2d-local-clifford-syndrome-space-depth-tradeoff.md]] in the large-ancilla regime: for good codes it gives Omega(n^{3/2}/m) rather than Omega(n/sqrt(m)).
  • It is a theorem about syndrome-extraction depth for stabilizer codes, not yet a lower bound stated in terms of CD(T_n,\mathfrak G).

Sources

  • 10.48550/arXiv.2302.04317 (Theorem 24, p. 12)