Skip to content

Fixed-Minor-Free Hardware Syndrome Depth Barrier

Claim/Theorem

Combining [[weighted-excluded-minor-separator-theorem.md]] with [[weighted-separator-function-to-syndrome-depth.md]] extends the current static-grid lower bound to bounded-degree fixed-minor-free hardware families.

Let \(C\) be a local Clifford stabilizer-measurement circuit on an \(N\)-qubit hardware graph \(G_{\mathrm{hw}}\) of maximum degree at most \(\Delta_{\mathrm{hw}}\), and suppose \(G_{\mathrm{hw}}\) excludes a fixed \(h\)-vertex minor \(H\). Assume \(C\) measures a bounded-weight local-expander quantum LDPC code with \(n\) data qubits. Put weight \(1\) on each data-qubit vertex and weight \(0\) on each ancilla vertex. Then there exists a separator \(X\) of size

\[ |X|\;=\;O(h^{3/2}\sqrt{N}) \]

such that each side outside the separator contains at most \(2n/3\) data qubits. Since at most \(|X|\) data qubits lie on the separator, each side in fact contains at least

\[ \frac{n}{3}-O(h^{3/2}\sqrt{N}) \]

data qubits. Therefore, whenever \(h^{3/2}\sqrt{N}=o(n)\), one can choose a circuit-qubit subset \(L\) with \(|D\cap L|=\Theta(n)\) and

\[ |\partial L|\;=\;O(\Delta_{\mathrm{hw}}\,h^{3/2}\sqrt{N}), \]

so [[weighted-separator-function-to-syndrome-depth.md]] yields

\[ \operatorname{depth}(C)\;=\;\Omega\!\left(\frac{n}{\Delta_{\mathrm{hw}}\,h^{3/2}\sqrt{N}}\right). \]

For bounded-degree fixed-minor-free hardware families this simplifies to

\[ \operatorname{depth}(C)\;=\;\Omega\!\left(\frac{n}{\sqrt{N}}\right), \]

and in the linear-space regime \(N=\Theta(n)\) one recovers

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

Thus the static near-square grid barrier is really one instance of a broader separator obstruction.

Dependencies

  • [[weighted-excluded-minor-separator-theorem.md]]
  • [[weighted-separator-function-to-syndrome-depth.md]]

Conflicts/Gaps

  • This remains a theorem about local Clifford stabilizer-measurement circuits, not yet arbitrary compilers or the full CD(T_n,\mathfrak G) functional.
  • The argument uses bounded hardware degree to convert a vertex separator into an edge-capacity bound. If the hardware degree grows with \(N\), the statement must be rescaled accordingly.
  • When \(\sqrt{N}\) is comparable to \(n\), the separator can absorb a non-negligible fraction of the data qubits and the clean Theta(n) balanced-cut statement weakens.
  • The node gives a fixed-minor-free theorem. Stronger genus-dependent constants are available in the bounded-genus literature but are not yet isolated on this graph.

Sources

  • 10.1145/100216.100254
  • 10.48550/arXiv.2109.14599