Skip to content

Hardware Cutwidth To Syndrome Depth

Claim/Theorem

This node is a source-grounded corollary schema rather than a named theorem from one paper.

Define the hardware cutwidth

\[ \operatorname{cw}(G_{\mathrm{hw}}) \;:=\; \min_{v_1,\dots,v_N} \max_t |\partial\{v_1,\dots,v_t\}|, \]

where the minimum runs over all linear orderings of the circuit qubits.

Let \(\mathcal S\) be a stabilizer space on n data qubits, represented by a full-row-rank matrix with kernel code \(C=\ker H\). Then any local Clifford syndrome-extraction circuit measuring a generating family of \(\mathcal S\) on \(G_{\mathrm{hw}}\) obeys

\[ \operatorname{depth}(C) \;\ge\; \frac{\operatorname{tw}(C)}{64\,\operatorname{cw}(G_{\mathrm{hw}})}, \]

where \(\operatorname{tw}(C)\) is the trellis-width of the associated classical kernel code \(C=\ker H\).

If that associated classical code has parameters [n,k_C,d_C], then combining this with Wolf's lower bound recorded in [[good-codes-have-some-linear-cut-rank.md]] yields

\[ \operatorname{depth}(C) \;\in\; \Omega\!\left( \frac{k_C(d_C-1)}{n\,\operatorname{cw}(G_{\mathrm{hw}})} \right) \]

for the measured stabilizer space.

For a near-square static 2D grid on \(N\) qubits, one has

\[ \operatorname{cw}(G_{\mathrm{hw}})=\Theta(\sqrt N), \]

because a column-major sweep gives an ordering with prefix boundary O(\sqrt N), while [[2d-grid-bisection-width.md]] gives the matching \Omega(\sqrt N) lower bound. Therefore

\[ \operatorname{depth}(C) \;\in\; \Omega\!\left( \frac{k_C(d_C-1)}{n\sqrt N} \right), \]

and this becomes Omega(sqrt(n)) only for measured families whose associated classical kernel codes have linear rate and linear distance.

So this route gives a clean intrinsic cutwidth lower bound, but not by itself a decisive proof for Quantum Tanner families, because [[qldpc-css-constituent-codes-not-good.md]] blocks the naive use of classical-code goodness for the measured constituent codes.

Dependencies

  • [[trellis-width-to-syndrome-depth-via-hardware-ordering.md]]
  • [[good-codes-have-some-linear-cut-rank.md]]
  • [[2d-grid-bisection-width.md]]

Conflicts/Gaps

  • Cutwidth controls only hardware families that admit a useful linear sweep. Separator-based families with poor cutwidth still need the more flexible reduction [[balanced-cut-rank-to-syndrome-depth.md]].
  • This theorem is still limited to stabilizer-measurement circuits and does not by itself define the full conjectured CD(T_n,\mathfrak G) functional.
  • For hardware families more general than static grids, cutwidth may be far from the right obstruction. The weighted-separator route remains strictly more general.
  • The lower bound depends on the associated classical kernel code, not directly on the quantum code parameters. For CSS qLDPC families this is a real limitation; see [[qldpc-css-constituent-codes-not-good.md]].

Sources

  • 10.48550/arXiv.2109.14599
  • 10.48550/arXiv.0805.2199
  • 10.48550/arXiv.0711.1383
  • 10.1016/S0166-218X(03)00265-8