The Intrinsic Cost of Quantum Syndrome Extraction

Chia-Tung Chu

Source-linked AI summary

The Intrinsic Cost of Quantum Syndrome Extraction

Chia-Tung Chu

arXiv:2609.39705v2Sep 30, 2026quant-phcs.ITmath.IT

TL;DR

Circuit-list and global-parameter bounds do not determine the interaction required across a particular hardware cut. The paper defines a generator-independent stabilizer cut cost and shows how it bounds exact extraction resources and, for a fixed family, layout bottleneck depth.

Problem
Existing bounds based on a chosen check list or global code parameters do not determine the interaction required across a particular hardware cut.
Source: §1 · p. 4
Method
The paper defines χU directly from the stabilizer space, independent of its generators, and relates it to exact crossing-resource costs under state-preserving syndrome extraction.
Source: §8 · p. 32
Results
Exact extraction needs at least χU/2 crossing two-qubit operations, while a fixed quantum Tanner family yields linear small-region costs and a tight square-grid space–depth tradeoff.
Source: §1.1 · pp. 6–7
Takeaways & Limitations
The cut cost assesses unavoidable interaction requirements before circuit choice and gives layout bottleneck depth guarantees for the specified fixed family.
Source: §1.1 · p. 6, §8 · p. 32
The constructions are ideal-circuit upper bounds and do not establish fault tolerance or minimum elapsed extraction time.
Source: §1.2 · p. 11, §8 · p. 32

Abstract

from arXiv · show

How much time is fundamentally required to extract the syndrome of a stabilizer code on hardware with a given connectivity graph? Previous bounds answer through a chosen list of checks (Delfosse, Beverland, and Tremblay, 2021) or through the global code parameters (Baspin, Fawzi, and Shayeghi, 2023). Here, we show that neither determines the interaction that a particular hardware cut requires. We therefore define the intrinsic cut cost, $\chi$, directly from the stabilizer group, independent of the generating set used to describe the code. It is computable from the check matrix alone, and equals the mutual information across the cut in the maximally mixed code state. We show that every exact extraction circuit, however adaptive, needs at least $\chi/2$ two-qubit operations across the cut, and alternatively with free local processing exactly $\chi$ shared Bell pairs. Guided by this intrinsic cut cost, we construct annular surface codes with constant-depth local extraction that give a counterexample to Corollary 1 of Delfosse, Beverland, and Tremblay. Furthermore, for a fixed quantum Tanner family, $\chi$ grows at least linearly with the size of every sufficiently small region, giving a depth guarantee at each corresponding bottleneck in every layout. This strengthens the global perspective of Baspin, Fawzi, and Shayeghi and, together with our matching square-grid construction, yields a tight space--depth tradeoff. Our results connect the interaction required by syndrome extraction to hardware communication capacity and thus provide a way to assess unavoidable circuit costs before committing to a particular layout.

1 Introduction

The introduction frames syndrome-extraction depth as a connectivity problem and motivates a cut-based account beyond bounds tied to a chosen check list or global code parameters. It presents the intrinsic cut cost as a stabilizer invariant governing interaction and entanglement across cuts, and outlines extensions to tree networks and weighted certificates alongside the results’ ideal-circuit scope and limits.

1 Introduction

DBT’s crossing-check count can change under equivalent generator recombination, whereas global parameters cannot locate interaction: appended fixed-|0⟩ qubits can leave a separated cut needing no crossing operations.These limitations motivate a cut-specific quantity rather than a bound from a chosen list or whole-code parameters.Source: §1 · pp. 4–5

1.1 Results

χ_U is independent of the generating list, computable from three check-matrix ranks, and equals the mutual information across the cut in the maximally mixed code state.Its formula is χ_U = rank H_U + rank H_Uc − rank H.Source: §1.1 · pp. 5–7
The intrinsic cut cost χ_U gives exact cut-level bounds: every exact circuit needs at least χ_U/2 crossing two-qubit operations, while χ_U shared Bell pairs suffice and are necessary with free local processing.For CNOT-only crossing operations, the lower bound is χ_U operations; with b boundary edges, the general depth bound is χ_U/(2b).Source: §1.1 · p. 7
For the [[144, 12, 12]] gross code, χ_U = 60 versus 144 Bell pairs per crossing incidence or 72 per crossing listed check; mitten codes have χ_U = 2g despite 4g crossing listed checks.On the 150-qubit mitten code, a generating set attaining 2g crossings must include finger generators of weight at least 28, so cut cost and sparsity can conflict.Source: §1.1 · p. 8
For the fixed quantum Tanner family, every sufficiently small region U has χ_U ≥ 2τ|U|, forcing depth at least τu/b behind a bottleneck with u data qubits and b boundary edges.This applies to every placement on any hardware graph; exact extraction is impossible if the region has no boundary edges.Source: §1.1 · pp. 8–9
An adaptive compiler achieves depth O_{w,δ}(max{1, n/N}) on a square grid, and the quantum Tanner family has optimal depth Θ(n²/N) for n ≤ N ≤ cn².The upper bound uses a fixed placement and counts routing, measurements, resets, corrections, and returning data qubits to their sites.Source: §1.1 · p. 9
Annular surface codes give bounded-weight expanding check lists yet admit depth-at-most-13 exact extraction, contradicting DBT’s claimed Ω(n_L/√N_L) lower bound.The list satisfies the hypotheses of Corollary 1 of DBT, but generator recombination preserves the measurement task while changing listed-check crossings.Source: §1.1 · p. 10
χU is computable from three check-matrix ranks and captures cut-dependent interaction that crossing-check counts can overestimate and global code parameters can miss.The paper presents it as a common quantitative basis for comparing code constructions, extraction compilers, and candidate hardware layouts.Source: §1.1 · p. 10

1.2 Discussion

For tree-connected processors, all edge budgets be ≥χUe can be met simultaneously using a vectorized syndrome projector prepared by the pure-state tree preparation theorem [YSM17, Theorem 5].Appendix F also extends the cut bound to weighted certificates and compares them with verified circuits for twelve published codes on fifteen hardware graphs.Source: §1.2 · p. 10
The lower bounds concern ideal, noiseless circuits and allow adaptivity, intermediate data measurements, and unlimited classical communication; Theorem 1.1 holds on every nonzero branch.The constructions are ideal-circuit upper bounds, and Theorem 1.4 uses long chains of Bell measurements whose errors would accumulate under noise.Source: §1.2 · pp. 10–11
The results do not establish fault tolerance, and optimizing crossing resources does not optimize elapsed local-processing depth.Under noise, discarded redundant checks may provide consistency information, whose value depends on the noise model and decoder; single-shot correction is left open [Bom15] [GTC+24].Source: §1.2 · p. 11
The discussion distinguishes the paper’s contribution as χU itself, branch-wise counts for crossing primitives, a uniform small-region estimate, and matching constructions.The mutual-information identification builds on stabilizer entropy calculations [FCY+04], while conversions between crossing CNOT or SWAP gates and shared Bell pairs use.Source: §1.2 · p. 11

2 Preliminaries and the measurement task

The section defines stabilizer-code syndrome extraction as a joint measurement that must preserve the quantum state within each syndrome sector. It specifies a hardware-local circuit model and explains what correctness must guarantee.

2.1 Checks, syndromes, and preserved information

The syndrome instrument projects onto each stabilizer sector while preserving arbitrary logical information and coherence within that sector.Generator changes may relabel syndrome bits by an invertible transformation, so circuits can measure a convenient generating set and reconstruct the requested syndrome classically.Source: §2.1 · pp. 11–12

2.2 The hardware and its cost

Hardware-local extraction uses edge-constrained one- and two-qubit instruments, product ancillas, and counted routing, while classical processing and communication are free.Data qubits must return to their original sites, separating quantum depth from decoder runtime and classical signal delay.Source: §2.2 · pp. 12–13

2.3 How much correctness must be tested?

Correctness on every pure state in every syndrome sector implies the full ideal instrument, including on superpositions and reference-entangled inputs.Correctness on a single promised sector or selected basis states is insufficient because it need not preserve superpositions.Source: §2.3 · pp. 13–14

3 The intrinsic cost of a cut

The intrinsic cut cost counts the independent stabilizer constraints that cannot be measured locally on either side of a data partition. It characterizes correlations and lower-bounds the crossing resources required for exact extraction, with matching resource costs under free local processing.

3.1 A generator-independent count

χ_U is the dimension of the stabilizer space modulo constraints supported wholly on either side, and equals the minimum number of crossing generators.Three binary ranks of the check matrix evaluate it without searching over generating sets.Source: §3.1 · pp. 14–15

3.2 Correlations and the measurement projector

For the maximally mixed code state, χ_U equals the mutual information across the cut; the syndrome-projector state has Schmidt rank 2^χ_U and entanglement entropy χ_U bits.The projector spectrum result holds at every cut, without a correctability assumption.Source: §3.2 · pp. 15–16

3.3 Crossing operations and circuit depth

Every exact adaptive extraction circuit requires at least χ_U/2 crossing two-qubit operations on each nonzero branch, and no crossing edge makes extraction impossible when χ_U is positive.The bound covers measurements and channels as well as gates; its constant depends on the crossing primitive counted as one operation.Source: §3.3 · pp. 16–17

3.4 Protocols that attain the cut cost

With free local processing, χ_U shared Bell pairs are necessary and sufficient; arbitrary crossing two-qubit instruments require at least ceil(χ_U/2) operations, with matching protocols.For crossing links with maximum matching size ν, the minimum crossing layers are ceil(χ_U/(2ν)) for arbitrary instruments and ceil(χ_U/ν) for CNOTs.Source: §3.4 · pp. 17–18
The matching resource protocols optimize crossing operations and layers, not total elapsed depth, because local state movement and processing take time on real devices.Different cuts may also require different adapted bases.Source: §3.4 · pp. 18–19

3.5 Approximate instruments

For approximate instruments, the crossing-count bound depends on fidelity, and with no boundary edge the fidelity must be at most 2^-χ_U.At fixed positive fidelity, approximation subtracts only a constant from the cut numerator; the bound concerns the full instrument, not syndrome probabilities alone.Source: §3.5 · p. 19

4 Worked examples and tree networks

The worked examples compare circuit resources with intrinsic cut costs across gross and mitten codes, then show that tree networks can attain every edge optimum simultaneously.

4.1 Sixty Bell pairs for a gross-code half-torus

For the gross-code half-torus, χU = 60, requiring exactly 60 shared Bell pairs under free local processing and admitting an optimum of 30 arbitrary crossing two-qubit gates.The 60-pair protocol retains 72 local and 60 crossing original weight-six checks and reconstructs all original outcome bits.Source: §4.1 · p. 20

4 Worked examples and tree networks

The examples distinguish exact crossing-resource optima from circuit sparsity, noisy-check utility, and elapsed depth.Redundant checks may provide noise-consistency information, while elapsed depth also depends on local gates, pair preparation, and storage.Source: §4.1 · p. 21, §4.2 · p. 21

4.2 Mitten codes and the thumb cut

For the mitten-code thumb cut, the exact cost is 2g shared Bell pairs, half the listed crossing-check count; at [[150, 30, 10]], attaining it requires finger generators of weight at least 28.The listed checks have weight nine, so the exact crossing cost does not determine the sparsity of an attaining circuit.Source: §4.2 · p. 21

4.3 Three circuits for four codes

For the three qLDPC codes, listed-check counts exceed χU by 12, 12, and 60, while incidence-based routing costs 2.4, 2.2, and 6 times the exact cost.The reductions separate transmitting each crossing check’s incidences from eliminating crossing checks through invertible recombination.Source: §4.3 · p. 22

4.4 Attaining all edge costs on a tree

On a tree, all edge minima χUe are simultaneously attainable, and the total Bell-pair optimum is the sum of the edge costs.The resource theorem assumes arbitrary local quantum processing, sufficient local memory, and free classical communication.Source: §4.4 · pp. 22–23

5 Why presentation expansion is insufficient

The annular construction shows that expansion of a chosen check presentation need not reflect intrinsic cut cost: an expanding presentation can still have constant-depth local extraction. This provides a counterexample to the cited local-expander depth conclusion while distinguishing presentation expansion from constraints inherent to the stabilizer space.

5 Why presentation expansion is insufficient

The intrinsic cut cost is invariant under invertible generator recombination, whereas a chosen presentation’s contracted Tanner graph can change substantially.Presentation edges indicate unavoidable communication only when their constraints cannot be eliminated by changing generators.Source: §5 · p. 23

5.1 An expanding annular presentation

For each annulus, the construction recombines disjoint black-vertex checks through a bounded-degree expander while keeping generator weight at most 132 and qubit incidence at most 36.The resulting contracted Tanner graph has at least |A|/18 boundary edges for every nonempty set A of at most nL/2 qubits.Source: §5.1 · p. 24

5.2 Consequences for local-expander bounds

An annular surface-code presentation has an expanding contracted Tanner graph but admits exact nearest-neighbor extraction at depth at most 13, contradicting the cited local-expander depth conclusion.The result applies to the stated version of Corollary 1 of DBT; its extraction constructions are unaffected.Source: §5.1 · p. 24, §5.2 · p. 25

5.1 An expanding annular presentation

A nearest-neighbor Clifford circuit of quantum depth at most 13 measures the recombined list exactly by reporting the original check outcomes through an invertible parity map.The circuit measures the original vertex and face checks, whose joint projectors coincide with those of the recombined list.Source: §5.1 · p. 24

5.2 Consequences for local-expander bounds

The multi-annulus examples retain bounded-depth extraction while allowing positive-rate subfamilies at fixed annulus size or growing distance as annulus size increases.They do not address simultaneous positive rate and growing distance; the expander supply is specified by a terminating finite search rather than an efficient construction.Source: §5.1 · p. 24, §5.2 · pp. 25–26

5.1 An expanding annular presentation

For the surface-code stabilizer space, a vertical cut has intrinsic cost O(L), matching its Θ(L) hardware boundary, even though the chosen expanding list has linearly many crossing generators.This explains why the circuit depth remains bounded as L grows.Source: §5.1 · p. 25

6 Uniform costs for small regions

Rate and distance alone do not ensure that every small region has substantial intrinsic cut cost. Under the full hypotheses of one fixed quantum Tanner construction, the paper proves a uniform volume law and converts it into depth bounds at individual hardware bottlenecks.

6.1 Why rate and distance are not enough

Good rate and distance do not guarantee positive cut cost on every small region: adding Θ(m) qubits fixed by weight-one Z checks leaves the global parameters good but gives those added subsets χU = 0.A uniform lower bound therefore needs information beyond rate and distance.Source: §6.1 · p. 26

6.2 The fixed-family volume law

For one fixed quantum Tanner family satisfying the construction’s hypotheses, every sufficiently small region is correctable and has entropy at least τ|U|, with constants independent of block length, region, and logical state.The result does not claim the same conclusion for arbitrary good quantum LDPC families; its constants depend on the fixed construction.Source: §6.2 · p. 27
The proof accounts for supported stabilizers formed by products whose outside components cancel by assigning them short descriptions and bounding the dimension of all such descriptions.The argument handles the full supported stabilizer space rather than counting only checks originally contained in the region.Source: §6.2 · p. 27

6.3 Individual hardware bottlenecks

For any placement, a region containing u eligible data qubits behind b > 0 hardware edges requires depth at least τu/b; with b = 0, exact extraction is infeasible.Internal routing can increase the required depth but cannot remove the boundary cost.Source: §6.3 · p. 28
The theorem’s uniform cut-cost bound also implies local expansion of any contracted Tanner graph whose generating presentation has bounded qubit incidence, while the converse fails.The converse fails because presentation expansion does not control cancellations among generators.Source: §6.3 · p. 28

7 Space and depth on grids

The paper relates small-region cut costs to geometric bottlenecks and gives an adaptive grid construction whose depth matches the lower-bound tradeoff for a fixed quantum Tanner family. The matching upper bound optimizes over a fixed placement and assumes free classical feedforward.

7.1 From a cut to a geometric lower bound

A weighted-separator argument extends the geometric lower bound to planar devices: depth is Ω(n/[∆hw shw(N)]) when the hereditary separator bound is sufficiently small relative to n.For hardware excluding a fixed minor, the cited separator theorem gives shw(N) = O(√N).Source: §7.1 · p. 29

7.2 An adaptive construction at every width

The adaptive construction implements bounded-weight, bounded-incidence commuting Pauli presentations on a full grid using a fixed data placement and exact extraction.It uses nearest-neighbor Clifford gates, measurements, resets, and free classical feedforward, and returns each data label to its input site.Source: §7.2 · pp. 29–30

7.3 The matching fixed-family tradeoff

The optimal tradeoff’s upper bound requires freedom to choose a fixed placement; a prescribed placement may concentrate data behind a narrow boundary, and the construction does not establish fault tolerance.It also uses intermediate measurements and free classical feedforward, and does not establish the same tradeoff for unitary gates followed by final readout.Source: §7.2 · p. 30, §7.3 · p. 32

7.2 An adaptive construction at every width

The grid compiler first measures checks with constant-depth layers of disjoint CNOTs, then routes each matching with mesh permutations on narrow grids or tiled entanglement swapping on wider grids.Tile-local Bell-pair preparation, Bell measurements, and classical corrections implement remote CNOTs in constant quantum depth per batch.Source: §7.2 · p. 30, Figure 2 · p. 31

7.3 The matching fixed-family tradeoff

For the fixed quantum Tanner family, the matching square-grid tradeoff has depth Θ(√n) at N = Θ(n) and Θ(1) at N = Θ(n2), with intermediate widths following the same law.The result is stated for full square-grid sizes in the stated range and minimizes over circuits and fixed data placements.Source: §7.3 · p. 32

8 Discussion

The discussion states what the intrinsic cut cost characterizes and how it supports depth guarantees, while identifying boundaries on layouts, networks, code families, and noisy extraction. Several extensions remain open beyond the settled models.

Discussion

The intrinsic cut cost gives exact single-cut resource requirements, while the fixed-family small-region theorem and adaptive grid compiler connect those costs to a space–depth tradeoff.The discussion distinguishes shared Bell pairs, crossing CNOTs, and arbitrary crossing two-qubit gates; it also notes that some questions remain beyond the models settled here.Source: §8 · p. 32

Prescribed layouts and elapsed depth

The grid compiler selects a placement, so its scaling does not characterize prescribed layouts; the gross-code construction attains a crossing-resource optimum, not minimum elapsed extraction time.Routing costs for prescribed placements, local processing and storage-transfer depth on modular devices, and upper bounds with final-readout-only measurements remain to be analyzed.Source: §8 · p. 32

Networks beyond trees

On trees, edge budgets can be attained together, but on cyclic networks individual cut inequalities need not characterize a feasible global resource allocation.A broader characterization must specify whether it counts delivered entangled pairs, elementary links, storage, or quantum depth for preparing the resource.Source: §8 · p. 33

Balanced cuts and other code families

The uniform Tanner theorem guarantees linear growth only for regions within a fixed small fraction of the block, not for all balanced cuts or other qLDPC families.Beyond the correctable range, regions may support logical observables; extending the result to another family requires control of products of checks that cancel outside the region.Source: §8 · p. 33

Noisy extraction

The compiler assumes perfect gates and measurements with unrestricted classical feedforward, so it does not establish a noise threshold or an efficient decoder.Errors in long resource chains can accumulate despite constant ideal quantum depth; reliable repeated extraction remains open.Source: §8 · p. 33

A Stabilizer algebra and measurement instruments

This appendix establishes algebraic and measurement-instrument identities used in the paper. It relates the intrinsic cut cost to check-matrix ranks and code-state correlations, then connects correctable regions to entanglement in pure code states.

A Stabilizer algebra and measurement instruments

The appendix proves its identities by relating local stabilizer ranks, syndrome-projector Schmidt decompositions, and complete measurement branches.The same analysis supplies a sectorwise correctness criterion and an approximate-instrument bound.Source: A Stabilizer algebra and measurement… · p. 34

A.1 Rank and local support

Subtracting the dimensions of stabilizers confined to each side from the full stabilizer dimension yields the intrinsic cut cost, independently of the check matrix.Rank-nullity expresses the confined dimensions through restrictions of the check matrix; ancilla columns add zero and do not change the identity.Source: §A.1 · p. 34

A.2 Correlations of the code state

The intrinsic cut cost is the mutual information between the two sides in the maximally mixed code state.The argument obtains the reduced-state entropies from the local stabilizer dimensions and compares them with the joint code-state entropy.Source: §A.2 · pp. 34–35
For a correctable region, bounding its supported stabilizer dimension lower-bounds its mutual information with the complement in the maximally mixed code state.The identity applies throughout the distance regime; for a general region, mutual information may also include classical correlations.Source: §A.2 · p. 35
For every pure code state, half the mutual information across a correctable cut is its entanglement entropy; the stated supported-stabilizer bound gives S(ψ_U) ≥ τ|U|.The bound holds for every region in the theorem’s stated correctable range.Source: §A.2 · p. 35

A.3 Syndrome projectors and adaptive trajectories

This section develops cut-wise bounds for syndrome extraction by analyzing complete and approximate trajectories and characterizing cut correlations in stabilizer normal form. It also presents parity-measurement and batching strategies that attain the corresponding crossing-operation and shared-Bell-pair costs, and relates the Bell-pair lower bound to prior entanglement-cost results.

A.3 Syndrome projectors and adaptive trajectories

Exact extraction forces every nonzero complete trajectory to implement its reported syndrome projector up to a scalar, yielding a cut bound that applies even with adaptive measurements.The projector decomposition holds for every syndrome and cut without a correctability assumption; crossing two-qubit operations imply χ_U ≤ 2g_L, while primitives of operator Schmidt rank at most two give χ_U ≤ g_L. A recorded Pauli frame is allowed when determined by the observed record; removing it takes at most one additional layer of local gates.Source: §A.3 · pp. 36–37

A.4 Approximate extraction on the reference input

For approximate extraction, the depth bound follows from trajectory Schmidt-rank growth and overlap with the ideal syndrome-projector state.The stated fidelity estimate is F ≤ 2^(2tb_L−χ_U); a diamond-distance guarantee with 2∥E−M_S∥⋄ ≤ ε gives the corresponding bound using overlap parameter 1−ε. The probability guarantee concerns the reference input, not arbitrary data inputs, and the same reference input can be used across cuts.Source: §A.4 · p. 40

B Attaining protocols and tree resources

The attaining-protocol results also use a sparse gross-code basis and projector-state reduction to make Bell-pair bounds for all tree edges attainable at once.The single-cut arguments allow unrestricted local processing and storage.Source: B Attaining protocols and tree resources · p. 41

B.1 The remote-parity protocol

A cut-adapted stabilizer basis reduces the protocol to measuring χ crossing parities with one shared Bell pair each, alongside local measurements.Each remote-parity gadget realizes the nondestructive parity measurement on every input, including inputs entangled with references; its extra raw bit is uniformly random given the parity. Summing branches and relabeling outcomes implements the required instrument without quantum operations conditioned on remote outcomes.Source: §B.1 · pp. 41–42

B.2 Shared pairs, crossing layers, and local storage

The single-cut costs are attainable with shared Bell pairs, and rank arguments give matching lower bounds on nonzero branches.The construction prepares χ shared pairs using ⌊χ/2⌋ crossing SWAP gates and, for odd χ, one crossing CNOT; the lower bounds are m ≥ χ shared pairs, at least χ crossing CNOT gates, and at least ⌈χ/2⌉ arbitrary crossing instruments.Source: §B.2 · p. 42
CNOT layers require B ≥ χ/ν, while arbitrary-instrument layers require B ≥ χ/(2ν); batching achieves the corresponding layer optima.With free local processing and sufficient storage, the constructions use χ CNOT slots or ⌈χ/2⌉ SWAP slots (plus one CNOT if χ is odd), distributed across at most ν crossing links per layer.Source: §B.2 · p. 43

B.3 A normal form for one cut

The cut normal form consists of p Bell pairs, q classically correlated pairs, and local product states, yielding mutual information 2p + q = χ.Here q = χ − 2p; local Clifford unitaries map the stabilizers to XX and ZZ generators for the Bell pairs, ZZ generators for the classically correlated pairs, and single-qubit Z operators.Source: §B.3 · p. 43

B.4 Reductions to prior entanglement-cost bounds

Prior results also imply the χ-ebit lower bound: nondestructive discrimination gives it via, and an instrument theorem gives it via [AMO26].The first route constructs K = 2^χ equally likely orthogonal maximally entangled syndrome eigenstates; the second uses branch Choi Schmidt number 2^χ to require at least χ Bell pairs.Source: §B.4 · p. 44

B.5 The gross-code matrix and its sparse certificate

This section develops matrix certificates for intrinsic cut costs and uses annular-code constructions to examine shallow local syndrome extraction. It presents a constant-depth local circuit that reports an exact syndrome and contradicts DBT’s Corollary 1 for independent lists with bounded generator weight and incidence, despite the stated disparity between crossing listed generators and circuit edges.

B.5 The gross-code matrix and its sparse certificate

χ_U = 60 for the gross code’s selected cut, and a sparse certificate yields an exact extraction using 60 Bell pairs, matching the lower bound.The retained basis has 72 local and 60 crossing checks; the original-check circuit has 144 crossing check–data interactions, while direct remote parity measurement uses 72 pairs. Both recover the full syndrome and preserve the syndrome-sector state.Source: §B.5 · p. 45

B.6 Matrix conventions for the further codes

The further-code audits report χ_U = 11 for a 12×12 rotated surface-code cut and χ_U = 132 for the specified two-gross cut.The rotated surface code has stabilizer dimension 143, with eleven crossing checks; the two-gross code has stabilizer dimension 276, and 144 of its 288 listed checks cross the cut. For the [[150, 30, 10]] mitten instance, specified cut costs range from 84 to 118; balanced-cut search values are upper bounds, not certified minima.Source: §B.6 · p. 46

B.7 The projector resource on a tree

On a tree, exact syndrome extraction is possible with χ_Ue Bell pairs on each edge, and each edge also requires at least that many by the cut lower bound.The construction prepares the projector resource state using edge Schmidt dimensions and local Bell-measurement protocols; necessity follows by grouping each side of an edge into one party.Source: §B.7 · p. 47

C Annular constructions

The annular construction separates expansion of a chosen check list from intrinsic stabilizer correlations by recombining surface-code checks while retaining extraction of the original local checks.The appendix applies this construction to a stated local-expander bound of DBT.Source: C Annular constructions · p. 47

C.1 Expanders and clique blow-ups

A bounded-degree expander with neighbor expansion at least |S|/4 transfers, through blocks of at most four vertices, to expansion at least |A|/18 for arbitrary vertex subsets.The clique blow-up result applies to all subsets, not only unions of blocks, and uses edges present in the constructed graph.Source: §C.1 · pp. 47–48

C.2 The annulus and its expanding presentation

The square-annulus code has distance L + 1, and its recombined presentation has generator weight at most 132, incidence at most 36, and contracted Tanner expansion at least |A|/18.The transformed black checks preserve the same signed stabilizer group; the expansion bound holds for every data subset of size at most half the qubits.Source: §C.2 · pp. 49–50

C.3 Nearest-neighbor extraction

Nearest-neighbor extraction of the original annular checks uses at most 13 quantum-depth layers, or 14 when classical output computation is counted.The circuit uses eight CNOT layers, no data-qubit measurement or reset, no long-range gate, and no preshared entanglement; its reported parities recover the transformed-check outcomes.Source: §C.3 · pp. 50–51

C.4 Several annuli

For m annuli, the tensor-product code has distance L + 1 and a globally recombined check presentation with weight at most 132, incidence at most 36, and expansion constant 1/18.The global expander connects blocks across different annuli, and the expansion bound holds for every data subset of size at most half the qubits.Source: §C.4 · p. 51
Each disjoint tile runs its local-check circuit simultaneously in thirteen layers, and reporting s = bTt gives exact conditional data maps, including for inputs entangled with a reference.Counting a separate final output layer raises the depth bound to fourteen [DBT21].Source: §C.4 · p. 51
The circuit is 1-local on a square patch of NL = (6L + 1)^2 qubits and uses only Clifford operations and Pauli measurement circuits as defined by DBT [DBT21].Counting only the active data and ancilla qubits gives NL = 32L^2 + 16L − 1, a constant fraction of the patch.Source: §C.4 · pp. 51–52
DBT’s slice-counting estimate remains valid, but for the annular family it yields Θ(nL) crossing generators where only O(√NL) circuit edges cross [DBT21].A slice can be chosen to contain between nL/2 − √NL and nL/2 data qubits.Source: §C.4 · p. 52
For sufficiently large L, the annular family has ncut = Θ(nL) listed generators crossing a slice but only O(√NL) circuit edges, so DBT’s Theorem 1 would imply depth Ω(L) despite depth at most 13 [DBT21].The family satisfies the local-expander assumptions with generator weight 132, incidence 36, α = 1/18, and ε = 1; the contradiction shows the theorem fails for these independent bounded-weight, bounded-incidence lists.Source: §C.4 · pp. 51–52

C.5 Generator changes and the DBT cut bound

Changing a stabilizer presentation can make the number of listed checks crossing a cut diverge from the interaction the measurement requires. The section gives constant-depth counterexamples to DBT bounds and states the distinct hypotheses needed to contradict its local-expander corollary.

C.5 Generator changes and the DBT cut bound

An independent list of t crossing checks can be recombined so that only one check crosses, while invertible outcome relabeling preserves the syndrome and conditional quantum output.The path construction measures the recombined checks in two matchings.Source: §C.5 · p. 52
A two-layer path circuit measures t independent checks crossing one cut, although DBT's bound is t/64 and is exceeded by the circuit's actual depth for t > 128.The generator bases have the same joint projectors under an invertible parity relabeling, and the construction uses the DBT measurement primitives described in the passage.Source: §C.5 · p. 52
For (ZA, ZAZB), the conditional mutual information used in DBT's lower-information argument vanishes, and χQ∩L = 0 matches an exact circuit with no crossing edge.The passage locates the failed proof step in removing conditioning, because the right partial parity reveals the right-side error component.Source: §C.5 · p. 53
With bounded weight and incidence, t disjoint copies plus one crossing check have ncut = t + 1 and |∂L| = 1, while the circuit remains constant-depth against a DBT lower bound of (t + 1)/64.The passage says these examples do not by themselves contradict the local-expander corollary because the bounded-incidence copies do not expand.Source: §C.5 · p. 53
The annular family supplies the bounded-weight, bounded-incidence, and expansion hypotheses needed for its constant-depth circuit to contradict DBT's Corollary 1 as stated.The section distinguishes this intrinsic-condition geometric argument from bounds based on aggregate code parameters.Source: §C.5 · p. 53
The adaptive lower-bound proof uses the operator Schmidt rank of each syndrome projector to constrain complete Kraus trajectories, without Clifford normalization or conditional-mutual-information comparisons.This avoids the invalid surjectivity inference identified in the DBT proof discussion.Source: §C.5 · pp. 52–53

D The uniform Tanner theorem and geometric bounds

The uniform Tanner theorem establishes positive density of shared stabilizer constraints in every sufficiently small region, which later parts use for geometric depth bounds.Construction graphs describe the code; hardware graphs describe allowed circuit operations.Source: D The uniform Tanner theorem and… · p. 53

D.1 Local representations in quantum Tanner codes

The proof bounds stabilizers supported in a small data region by representing them through local coefficient spaces and controlling relations, support, and boundary overlap. Uniform construction hypotheses then yield a strict dimension deficit for every sufficiently small region.

D.1 Local representations in quantum Tanner codes

A nonzero coefficient relation must have at least σiM nonzero vertex components, because local distance lower-bounds its coordinates while mixing limits internal diagonal edges.This lower bound on relation support is used to make sparse representations unique and linear.Source: §D.1 · p. 55
Reduction using local component-code words represents each sufficiently small supported image with few vertex components; a gap from relation support makes that representation unique and linear.The argument applies to both CSS sectors using the component and dual-code hypotheses.Source: §D.1 · pp. 55–56
Linearity bounds the union of representative supports by comparing each vertex's nonzero projections across the representation space with the per-element component bound.This yields control of the set of vertices used by any representative, not just an individual tuple.Source: §D.1 · p. 56
Local distance and Singleton bounds limit supported dimensions using only internal squares and boundary squares belonging to U; mixing controls overlap between the two CSS boundary sets.The overlap control is needed because adding the separate local bounds alone does not produce the required deficit.Source: §D.1 · pp. 56–57
The small-region bound applies down to U = ∅, so the code estimate is available before a hardware partition is chosen; only the later geometric choice needs a positive size interval.Uniform constants retain a positive gap between distance and mixing, with the resulting region-size fraction depending on the construction's reduction constants.Source: §D.1 · pp. 57–58
For every sufficiently small region U, the supported stabilizer dimension is bounded below |U| by a uniform fraction, yielding χU(S) ≥ 2τ0|U| under the stated family hypotheses.The constants depend on uniform reduction constants, and the geometric application imposes an additional size threshold.Source: §D.1 · pp. 57–58

D.2 Proof of the intrinsic bound on square patches

A vertical sweep through the patch selects a cut whose data region lies in the range of the intrinsic small-region bound while its hardware boundary is controlled by the interaction-range limit. Applying the cut lower bound gives the geometric depth guarantee.

D.2 Proof of the intrinsic bound on square patches

Some sweep cut has a data region U with ηn/4 ≤ |U| ≤ ηn/2, where the intrinsic estimate gives χU ≥ γηn/4 > 0.The sweep adds one column at a time, and the number of data sites rises from zero to more than ηn/2.Source: §D.2 · p. 58
For a patch of interaction range b, the sweep boundary satisfies |∂Lu| ≤ b²(2b + 1)N, using only the range bound and not graph connectivity.Only sites in the last b columns can have neighbors outside the swept region.Source: §D.2 · p. 58
If the selected boundary is empty, exact extraction is ruled out; otherwise the intrinsic cut bound yields the stated depth guarantee, with a separate single-qubit cut argument for N < 1.The single-qubit case applies when ηn ≥ 2.Source: §D.2 · p. 58

D.3 Weighted separators

Weighted separators turn local lower bounds on intrinsic cut cost into depth bounds by selecting a suitably sized data region with a controlled hardware boundary. This applies both to general stabilizer spaces satisfying the stated condition and, with additional assumptions, to quantum Tanner codes on fixed-minor-free hardware.

D.3 Weighted separators

The recursion selects a region containing between ηn/8 and ηn/2 data qubits, the interval needed to apply the code estimate.Data vertices receive weight one and ancillas weight zero; repeated separators control the selected region’s boundary.Source: §D.3 · pp. 59–60
For fixed α, η and shw(N) = o(n), the separator argument gives depth Ω(n/[∆hwshw(N)]).It selects a region whose data size lies in the code-estimate interval, then compares its cut-cost lower bound with the available crossing operations.Source: §D.3 · pp. 59–60
The code condition requires χQ∩L(S) > αηn/8 for the selected region; a zero boundary makes exact measurement infeasible.For a positive boundary, this cut-cost lower bound yields the depth bound when divided by the boundary estimate.Source: §D.3 · pp. 59–60
For fixed h, α, η, bounded degree, and N = Θ(n), fixed-minor-free hardware gives depth Ω(√n).The argument uses a weighted separator bound of h3/2√N for hardware graphs excluding an h-vertex minor.Source: §D.3 · p. 60
For the quantum Tanner family, fixed h, η, τ, bounded degree, and N = Θ(nj) imply depth Ω(√nj) on h-minor-free hardware.The conclusion follows by applying the fixed-minor-free bound using the family’s code estimate with α = 2τ.Source: §D.3 · pp. 60–61

D.4 The existing partition method with data-weighted separators

The existing partition method combines entanglement bounds across correctable parts with data-weighted separators to obtain a depth certificate. The grid compilation constructs exact syndrome extraction by measuring disjoint checks, routing interaction pairs in batches, and preparing and fusing local Bell resources.

D.4 The existing partition method with data-weighted separators

The partition argument bounds depth using total correctable-part entanglement and a separator-built hardware partition, retaining a conservative factor of 3.The derivation first bounds entanglement growth from product input, then lower-bounds entanglement across correctable parts; its rank argument improves the denominator from 3Bv to Bv.Source: §D.4 · pp. 61–62
Data-weighted separators construct a partition with fewer than d data qubits per part, and every inter-part edge meets the union of separators.For fixed-minor-free bounded-degree hardware, the resulting bound applies to good stabilizer families without a uniform lower bound on χU for every small subset.Source: §D.4 · p. 62

E.1 Measuring disjoint checks without check ancillas

Disjoint-support check sets are measured in sequence, yielding the exact joint Lüders instrument even on inputs entangled with an untouched reference.The checks are colored into disjoint supports, and each color’s circuit uses at most 2(w −1) CNOT matchings plus five additional layers.Source: §E.1 · pp. 62–63

E.2 Fixed terminals and batches of routes

A logical matching is divided into at most 2h −1 batches so pairs in each batch use disjoint tile rows.Pairs in different rows route through distinct columns; the routes are edge-disjoint and require only constant switching within each tile.Source: §E.2 · p. 63

E.3 Local Bell preparation and simultaneous fusion

Local port pairs are prepared as Bell states without disturbing data or spectator registers, then Bell measurements fuse route resources into endpoint pairs.The local preparation takes at most forty layers, and the fusion measurements plus parity corrections take four more layers.Source: §E.3 · pp. 63–64

E.4 Remote gates, the mesh fallback, and total depth

The grid compiler implements remote gates either with routed Bell resources or, in the narrow-grid regime, with mesh permutations. The accompanying appendix develops weighted-cut certificates and reports verified extraction circuits on fixed hardware graphs.

E.4 Remote gates, the mesh fallback, and total depth

51 layers suffice for one tiled routing batch, including Bell preparation, fusion, correction, and remote CNOTs, with no Bell state supplied for free.Ancillas are reset and reused between batches; every refined remote-gate branch is a scalar multiple of the intended CNOT.Source: §E.4 · p. 64
When q2 < n, mesh permutations implement the logical circuit in at most 18L + 1 CNOT-alphabet layers and return data to their fixed sites.The two routing regimes together establish the stated depth bound across N ≥ n and its bounded-aspect-ratio extension.Source: §E.4 · pp. 64–65

F.1 Weighted-cut certificates

Weighted-cut certificates combine several regions’ cut costs with vertex potentials to certify a bound on two-qubit-operation layers.A single region with weight one recovers a vertex-cover special case; rational feasible certificates can be checked exactly.Source: §F.1 · p. 65

F.2 Verified circuits on fixed hardware graphs

The certificate study covers twelve published codes on fifteen hardware graphs, using fixed code presentations, placements, graphs, and explicit circuits.Circuits are verified as exact syndrome instruments on arbitrary inputs, including inputs entangled with an untouched reference.Source: §F.2 · p. 66

F.3 Reading the table

Table 5 places certified lower bounds beside verified circuit layer counts for published-code extraction circuits. The discussion contrasts cases where the bounds are close to the circuit depths with cases where they leave substantial gaps.

F.3 Reading the table

On Tanner incidence graphs, certified bounds are one or two general layers and two or three rank-two layers, while circuits use four to fifteen CNOT layers.The broad boundaries of Tanner incidence graphs yield weak cut bounds; listed-check incidence explains the reported depths for several circuits.Source: §F.3 · pp. 66–67, Table 5 · p. 67
On local grids, surface-code rank-two bounds are three layers against four CNOT layers, while moving the [[58, 16]] code to a bus grid raises its bound from three to eight.For that code, verified two-qubit depth also rises from eight on its Tanner graph to sixty on the bus grid.Source: §F.3 · p. 67, Table 5 · p. 67
The noiseless, exact circuits and bounds do not establish fault tolerance, and finite region searches cannot rule out stronger certificates.Remaining gaps on the bus grids are open, with gadget routing constants setting the reported depths at these sizes.Source: §F.3 · p. 67