Trellis Width To Syndrome Depth Via Hardware Ordering

Claim/Theorem

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

Let \(\mathcal S\) be a stabilizer space on a data-qubit set \(D\) of size \(n\), represented by a full-row-rank binary matrix \(H\) with kernel \(C=\ker H\). Let \(G_{\mathrm{hw}}\) be a hardware graph on all circuit qubits, and fix an ordering

\[ v_1,v_2,\dots,v_N \]

of all circuit qubits. For each prefix

\[ L_t=\{v_1,\dots,v_t\}, \]

assume the hardware cut satisfies

\[ |\partial L_t|\;\le\;b \qquad \text{for all }t. \]

Let \(\pi\) be the induced ordering of the data qubits \(D\) obtained by deleting ancillas from the hardware ordering, and let \(P_i^\pi\) be the first \(i\) data qubits in that order. Define the ordering-specific connectivity width

\[ \tau_\pi(\mathcal S) \;:=\; \max_i \chi_{P_i^\pi}(\mathcal S). \]

Then any local Clifford syndrome-extraction circuit measuring a generating family of \(\mathcal S\) on \(G_{\mathrm{hw}}\) obeys

\[ \operatorname{depth}(C) \;\ge\; \frac{\tau_\pi(\mathcal S)}{64\,b}. \]

Moreover, by [[cross-cut-stabilizer-rank-rank-formula.md]], \(\tau_\pi(\mathcal S)\) is exactly the trellis-width profile of the classical code \(C=\ker H\) along the ordering \(\pi\). Since the usual trellis width is the minimum of this quantity over all orderings, one obtains the presentation-invariant bound

\[ \operatorname{depth}(C) \;\ge\; \frac{\operatorname{tw}(C)}{64\,b}, \]

where \(\operatorname{tw}(C)\) denotes code trellis-width of the associated classical kernel code \(C=\ker H\). If that 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]] gives

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

for the measured stabilizer space.

Proof sketch:

1. Every data-prefix \(P_i^\pi\) occurs as \(D\cap L_t\) for the hardware prefix ending at the \(i\)-th data qubit in the full ordering.
2. Ancilla locations do not affect \(\chi_L(\mathcal S)\) because the measured stabilizer space acts only on the data qubits, so

\[ \chi_{L_t}(\mathcal S)=\chi_{P_i^\pi}(\mathcal S). \]

1. Apply [[stabilizer-cut-rank-functional.md]] to that prefix cut and maximize over \(i\).

Thus any hardware family admitting a small-boundary linear sweep converts code trellis-width directly into a syndrome-depth lower bound.

Dependencies

• [[cross-cut-stabilizer-rank-rank-formula.md]]
• [[good-codes-have-some-linear-cut-rank.md]]
• [[stabilizer-cut-rank-functional.md]]

Conflicts/Gaps

• This route uses only prefix cuts from one hardware ordering. It does not capture lower bounds that fundamentally require more general separators.
• The theorem is still inside the stabilizer-measurement model and does not yet identify a fully compiler-native congestion-dilation quantity.
• For general hardware families, the useful parameter is the minimum achievable prefix boundary b; the current graph does not yet package that parameter into a standalone hardware invariant.
• The lower bound depends on the classical parameters of \(C=\ker H\), not automatically on the quantum code parameters of the measured stabilizer code. For CSS qLDPC families this is a real limitation rather than a technicality; see [[qldpc-css-constituent-codes-not-good.md]].
• For static 2D grids this route becomes sharp only when one can separately prove linear trellis width of the associated classical kernel code. The current graph does not yet have such a theorem for the constituent classical codes in Quantum Tanner constructions.

Sources

• 10.48550/arXiv.2109.14599
• 10.48550/arXiv.0805.2199
• 10.48550/arXiv.0711.1383