Skip to content

Submodular Cut Congestion Lower Bounds SWAP-Only Compiler Depth

Claim/Theorem

Let \(\mathcal S\) be a stabilizer space on qubit set \(Q\), and let

\[ T_{\mathrm{sub}}(\mathcal S):=(Q,\lambda_{\mathcal S}), \qquad \lambda_{\mathcal S}(L):=\chi_L(\mathcal S). \]

For a hardware graph \(G_{\mathrm{hw}}\) on the same qubit locations, define the submodular cut-congestion functional

\[ \operatorname{CD}_{\mathrm{sub}}(T_{\mathrm{sub}}(\mathcal S),G_{\mathrm{hw}}) \;:=\; \max_{L\subseteq Q,\ |\partial_{G_{\mathrm{hw}}}L|>0} \frac{\lambda_{\mathcal S}(L)}{|\partial_{G_{\mathrm{hw}}}L|}. \]

Then every measurement-free SWAP-only syndrome-extraction circuit \(C\) for \(\mathcal S\) on hardware \(G_{\mathrm{hw}}\) obeys

\[ \operatorname{depth}(C) \;\ge\; \frac{1}{16}\, \operatorname{CD}_{\mathrm{sub}}(T_{\mathrm{sub}}(\mathcal S),G_{\mathrm{hw}}). \]

Equivalently,

\[ \operatorname{depth}(C) \;\ge\; \frac{1}{16}\, \max_{L\subseteq Q,\ |\partial_{G_{\mathrm{hw}}}L|>0} \frac{\chi_L(\mathcal S)}{|\partial_{G_{\mathrm{hw}}}L|}. \]

So once the guest object is allowed to be a canonical symmetric submodular demand function rather than an ordinary graph, the desired compiler-native CD(T_n,G) statement is already available in the measurement-free SWAP-only regime.

Proof skeleton:

  1. [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]] shows that \(T_{\mathrm{sub}}(\mathcal S)\) is canonical and that
\[ \operatorname{serv}_L(C)\;\ge\;\frac{1}{16}\,\lambda_{\mathcal S}(L) \]

for every hardware cut \(L\). 2. In a SWAP-only depth layer, each hardware edge is used by at most one two-qubit gate. Hence across any fixed cut \(L\), one layer contributes at most \(|\partial_{G_{\mathrm{hw}}}L|\) units of cross-cut service. 3. Summing over all depth layers gives

\[ \operatorname{serv}_L(C) \;\le\; \operatorname{depth}(C)\,|\partial_{G_{\mathrm{hw}}}L|. \]
  1. Combining the lower and upper bounds yields
\[ \operatorname{depth}(C) \;\ge\; \frac{\lambda_{\mathcal S}(L)}{16\,|\partial_{G_{\mathrm{hw}}}L|} \]

for every cut \(L\), and maximizing over \(L\) proves the theorem.

This is the precise sense in which the canonical submodular demand object already yields a theorem-level compiler-native lower bound. The remaining gap is only if one insists on a more classical routing presentation: explicit paths, packet demands, or a guest graph rather than a cut functional.

Linked branch decompositions from [[linked-branch-decomposition-exists-at-optimal-width.md]] remain useful only as structural certificates for the submodular demand object. By themselves they do not improve the depth lower bound above, because the proof still bottlenecks on hardware cut capacity \(|\partial L|\) rather than on any abstract decomposition width.

Dependencies

  • [[stabilizer-cut-rank-defines-canonical-submodular-cd-object.md]]
  • [[cross-cut-gate-service-lower-bounds-stabilizer-cut-rank.md]]
  • [[swap-only-compiler-extraction-reduces-cd-to-stabilizer-cut-rank.md]]
  • [[linked-branch-decomposition-exists-at-optimal-width.md]]

Conflicts/Gaps

  • This theorem is cut-based, not path-based. It settles a submodular CD formulation, but not a packet-routing or guest-graph formulation.
  • The statement remains confined to measurement-free SWAP-only unitary compilers with final local measurements.
  • Linked or lean decompositions may still help prove large values of \(\operatorname{CD}_{\mathrm{sub}}\) for explicit code families, but they are not needed to derive compiler depth from service once \(\lambda_{\mathcal S}\) is known.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1006/jctb.2001.2082