Skip to content

Balanced Cut-Rank To Syndrome Depth

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, and let \(G_{\mathrm{hw}}\) be a bounded-degree hardware graph family with weighted separator function \(s_{\mathrm{hw}}(N)\) as in [[weighted-separator-function-to-syndrome-depth.md]]. Assume there exist constants \(\varepsilon\in(0,1/2]\) and \(\alpha>0\) such that for every qubit subset \(L\) with

\[ \varepsilon n \;\le\; |L\cap D| \;\le\; (1-\varepsilon)n, \]

the intrinsic cross-cut stabilizer rank satisfies

\[ \chi_L(\mathcal S)\;\ge\;\alpha n. \]

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

\[ \operatorname{depth}(C) \;\in\; \Omega\!\left( \frac{n}{\Delta_{\mathrm{hw}}\,s_{\mathrm{hw}}(N)} \right), \]

where \(\Delta_{\mathrm{hw}}\) is the hardware maximum degree.

In particular, on a static near-square 2D grid with N=Theta(n) and \(s_{\mathrm{hw}}(N)=\Theta(\sqrt{N})\),

\[ \operatorname{depth}(C)\;=\;\Omega(\sqrt{n}). \]

Proof sketch:

  1. [[weighted-separator-function-to-syndrome-depth.md]] gives a data-balanced circuit cut \(L\) with
\[ |\partial L|\;=\;O(\Delta_{\mathrm{hw}}\,s_{\mathrm{hw}}(N)). \]
  1. By the present hypothesis, that same cut has \(\chi_L(\mathcal S)\ge \alpha n\).
  2. Apply [[stabilizer-cut-rank-functional.md]] cut by cut to obtain the stated depth lower bound.

So the remaining invariant route to Conjecture 3 can be stated exactly: prove a linear lower bound on \(\chi_L(\mathcal S)\) for all hardware-balanced cuts of the relevant expander-style QLDPC stabilizer spaces.

Dependencies

  • [[stabilizer-cut-rank-functional.md]]
  • [[weighted-separator-function-to-syndrome-depth.md]]

Conflicts/Gaps

  • This node is only a reduction criterion. It does not prove the hypothesis for Quantum Tanner codes or for any other explicit expander-style QLDPC family.
  • [[good-code-parameters-do-not-imply-cut-rank.md]] shows that good [n,k,d] parameters alone are insufficient to force the hypothesis.
  • [[good-codes-have-some-linear-cut-rank.md]] and [[good-codes-have-logarithmic-branchwidth.md]] show that good codes already force nontrivial intrinsic connectivity, but they still fall short of the balanced, hardware-compatible form needed here.
  • The statement remains inside the stabilizer-measurement model. Lifting it to a fully compiler-native CD(T_n,\mathfrak G) theorem is still open.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1145/100216.100254