Lesson 08 - Syndrome Extraction and Hardware Constraints¶
Prerequisites And Diagnostic Checks¶
Ask:
- How do you measure one Pauli stabilizer with an ancilla?
- Why are surface-code checks easy to schedule on a 2D grid?
- What is a hardware connectivity graph?
- What does a balanced cut limit physically?
Concrete Motivation From The Research Map¶
The previous lessons explained why expander-style QLDPC codes have strong nonlocal check structure. This lesson asks what happens when those checks must be measured on constrained hardware.
The slogan is:
syndrome extraction turns Tanner edges into physical service demands.
Stabilizer Measurement Circuits¶
To measure one Z-type stabilizer, prepare an ancilla, interact it with each data qubit in the support of the stabilizer, measure the ancilla, and reset or discard it. X-type checks are analogous up to basis changes.
For a surface code, the check support is geometrically local. The ancilla can sit near the data qubits. Constant-weight checks are also constant-diameter checks.
For a QLDPC code, constant weight does not imply constant diameter on a 2D chip. A check may touch only \(6\) qubits, but those qubits can be far apart in the hardware layout.
Why Hardware Locality Matters¶
The hardware graph \(G_{\mathrm{hw}}\) records native two-qubit interactions. If two qubits are adjacent in this graph, they can interact in one layer. If they are far apart, the compiler must create an effective interaction using allowed local operations.
The code's Tanner graph says what must interact. The hardware graph says what can interact cheaply.
SWAP Gates As A Routing Primitive¶
In a SWAP-only model, qubit states move through the hardware graph by nearest-neighbor SWAPs. A nonlocal Tanner edge becomes a path in the hardware graph.
If the path is long, the interaction has high dilation. If many paths share the same hardware edge or cut, the implementation has high congestion.
SWAP-only routing is not the most general possible model, but it is a clean minimal model. If even more powerful local Clifford syndrome-extraction models have a lower bound, SWAP-only models inherit it.
Congestion¶
Congestion measures crowding. If many required interactions must cross the same small hardware cut, they cannot all be serviced in one time step.
For a fixed hardware cut \(L\), one circuit layer can use at most \(|\partial L|\) edges across that cut. If the code demands \(\Omega(n)\) independent cross-cut syndrome information, then depth is at least demand divided by capacity.
Dilation¶
Dilation measures distance. If a required interaction is routed along a path of length \(\ell\), it cannot be completed in less than order \(\ell\) local movement or interaction steps in a simple routing model.
Congestion and dilation capture different obstructions:
- dilation: one demand is far away
- congestion: many demands compete for the same narrow channel
The CD(T_n,G) Functional¶
The original Conjecture 3 language uses a congestion-dilation object for mapping a guest Tanner graph \(T_n\) into a hardware graph \(G\).
The research graph now separates several related objects:
- ordinary guest-graph routing
- stabilizer cut-rank demand
- canonical submodular demand
- SWAP-only compiler lower bounds
This separation matters because stabilizer demand is not always faithfully represented by an ordinary graph cut function.
Static 2D Lower Bound¶
The local node 2d-local-clifford-syndrome-space-depth-tradeoff.md records a theorem:
for 2D local Clifford syndrome-extraction circuits for local-expander QLDPC codes on square patches with \(N_i\) total qubits.
When \(N_i=\Theta(n_i)\), this gives
This is already stronger than a SWAP-only lower bound for the same static 2D setting, because the circuit model is more permissive.
Expansion Cut To Syndrome Depth¶
The invariant cut form is:
If a balanced cut has small boundary and the code forces large cross-cut syndrome demand, depth must be large.
On a near-square 2D grid, \(|\partial L|=O(\sqrt N)\), recovering the static 2D barrier.
Space-Depth Tradeoff¶
The lower bound says:
To make depth constant using this bound, one needs roughly \(N=\Omega(n^2)\) physical qubits. Extra area buys cut capacity.
That is the space-depth tradeoff: better depth is possible only by paying with more hardware resources or by leaving the static 2D model.
What This Does And Does Not Prove¶
Proved in the local graph:
- static 2D local Clifford syndrome-extraction barriers for local-expander QLDPC families
- separator-style cut lower bounds
- a stabilizer cut-rank functional for intrinsic cross-cut demand
- a submodular cut-congestion lower bound for measurement-free SWAP-only syndrome extraction
Still not the same as the original broad conjecture:
- a classical guest-graph routing interpretation of every stabilizer demand
- a fully general compiler-independent
CD(T_n,G)theorem - a complete bridge from every desired QLDPC presentation to the needed intrinsic cut-rank lower bounds
Active Recall¶
- What is the difference between check weight and check diameter?
- Define congestion using a hardware cut.
- Define dilation using a routed path.
- Why does the local Clifford theorem imply the SWAP-only static 2D lower bound a fortiori?
- What remains open beyond the static 2D theorem?
Next-Step Handoff¶
The final lesson teaches how to read the Conjecture 3 research map as a proof frontier rather than as a pile of unfamiliar nodes.