Skip to content

Code Branchwidth To Syndrome Depth Via Hardware Tree Decomposition

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 n data qubits, represented by a full-row-rank matrix with kernel code \(C=\ker H\). Consider a cubic tree \(T\) whose leaves are all circuit qubits, and for each edge \(e\in E(T)\) let \(L_e\) be one of the two leaf sets displayed by cutting \(e\). Assume every such hardware cut has boundary

\[ |\partial L_e|\;\le\;b. \]

Delete the ancilla leaves from \(T\) and suppress degree-2 vertices to obtain a cubic tree \(T_D\) on the data qubits alone. Then some edge-displayed data cut \(L\) of \(T_D\) satisfies

\[ \chi_L(\mathcal S)\;\ge\;\sigma(C), \]

where \(\sigma(C)\) is the code branchwidth from [[good-codes-have-logarithmic-branchwidth.md]]. Therefore any local Clifford syndrome-extraction circuit measuring a generating family of \(\mathcal S\) on the hardware graph obeys

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

If the associated classical kernel code \(C=\ker H\) has parameters [n,k_C,d_C], then combining this with [[good-codes-have-logarithmic-branchwidth.md]] gives

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

for the measured stabilizer space.

So any hardware family admitting a small-width tree decomposition of its qubit set already forces superconstant syndrome-extraction depth for good codes, even without proving linear balanced-cut connectivity.

Proof sketch:

  1. By [[cross-cut-stabilizer-rank-rank-formula.md]], code branchwidth is the minimum over cubic trees on the data coordinates of the maximum displayed intrinsic cut-rank.
  2. The induced data tree \(T_D\) is one such cubic tree, so some displayed data cut has \(\chi_L(\mathcal S)\ge \sigma(C)\).
  3. That data cut comes from an edge cut of the original hardware tree whose boundary is at most \(b\).
  4. Apply [[stabilizer-cut-rank-functional.md]] to that hardware cut.

This is the tree-decomposition analogue of [[trellis-width-to-syndrome-depth-via-hardware-ordering.md]], with branchwidth replacing trellis-width and a general cubic tree replacing a path.

Dependencies

  • [[cross-cut-stabilizer-rank-rank-formula.md]]
  • [[good-codes-have-logarithmic-branchwidth.md]]
  • [[stabilizer-cut-rank-functional.md]]
  • [[trellis-width-to-syndrome-depth-via-hardware-ordering.md]]

Conflicts/Gaps

  • Because the current branchwidth lower bound for good codes is only Omega(n/log n), this route is asymptotically weaker than the cutwidth / trellis-width route on static grids.
  • The useful hardware parameter here is a tree-decomposition cut width of the qubit set; the current graph does not yet identify the optimal standard graph invariant for this role.
  • The theorem still lives inside the stabilizer-measurement model and does not yet define the full compiler-native CD(T_n,\mathfrak G) object.
  • This route does not eliminate the need for stronger structure such as balanced linear \chi_L if one wants the sharp Omega(n/sqrt N) law on broad separator families rather than only sweep-like or tree-decomposable families.
  • As with the cutwidth route, the lower bound depends on the classical kernel code rather than directly on the quantum code parameters. For CSS qLDPC families this makes the route conditional rather than decisive; see [[qldpc-css-constituent-codes-not-good.md]].

Sources

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