Skip to content

Weighted Separator Function To Syndrome Depth

Claim/Theorem

This node is a source-grounded corollary schema rather than a named theorem from one paper. Let \(G_{\mathrm{hw}}\) be an \(N\)-vertex hardware graph of maximum degree at most \(\Delta_{\mathrm{hw}}\). Assume the hardware family admits a weighted separator function \(s_{\mathrm{hw}}(N)\) in the following sense: for every induced subgraph \(H\) of \(G_{\mathrm{hw}}\) with at most \(N\) vertices and every nonnegative vertex-weight function \(w\) on \(H\), there exists a separation \((A,B)\) of \(H\) with

\[ |A\cap B|\;\le\;s_{\mathrm{hw}}(N), \]

and

\[ w(A\setminus B),\;w(B\setminus A)\;\le\;\frac{2}{3}\,w(V(H)). \]

Now suppose a local Clifford stabilizer-measurement circuit on \(G_{\mathrm{hw}}\) measures a bounded-weight local-expander quantum LDPC code with \(n\) data qubits. Put weight \(1\) on data-qubit vertices and weight \(0\) on ancillas. Then, provided \(s_{\mathrm{hw}}(N)=o(n)\), there exists a subset \(L\) of circuit qubits with \(|D\cap L|=\Theta(n)\) and

\[ |\partial L|\;=\;O(\Delta_{\mathrm{hw}}\,s_{\mathrm{hw}}(N)). \]

Applying [[expansion-cut-to-syndrome-depth.md]] yields

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

Therefore any sublinear weighted-separator profile on the hardware graph family forces superconstant syndrome-extraction depth for local-expander QLDPC families, and the static-grid law Omega(n/sqrt(N)) is just the specialization \(s_{\mathrm{hw}}(N)=Theta(\sqrt{N})\).

Dependencies

  • [[expansion-cut-to-syndrome-depth.md]]

Conflicts/Gaps

  • This is still a theorem about local Clifford stabilizer-measurement circuits, not arbitrary compilation maps or the full CD(T_n,\mathfrak G) conjecture.
  • The argument requires bounded hardware degree to convert separator size into edge-boundary capacity.
  • The balanced-cut conclusion is useful only when \(s_{\mathrm{hw}}(N)=o(n)\); otherwise the separator can absorb too many data qubits.
  • The node is a meta-corollary: to use it one still needs a genuine weighted separator theorem for the chosen hardware family.

Sources

  • 10.48550/arXiv.2109.14599
  • 10.1145/100216.100254