A lower bound on the overhead of addressable surgery on sparse stabiliser codes

arXiv:2610.11097 · quant-ph · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "A lower bound on the overhead of addressable surgery on sparse stabiliser codes".

Mira: The gist: Performing lattice surgery on sparse stabiliser codes with sparse ancillas requires an overhead of at least ˜ k squared ancillary qubits in the worst case,

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So, this paper is called "A lower bound on the overhead of addressable surgery on sparse stabiliser codes," and it's looking at how much ancillary qubit space you actually need when you perform lattice surgery on these stabilizer codes. The main point they make is that for sparse stabiliser codes, performing this kind of lattice surgery with sparse ancillas requires a minimum overhead of (two) qubits in the worst case <ref:2610.11097#pg1,qubits in the worst case>.

Mira: That's a pretty strong claim, Kai. What it means is that for codes where k gets really large, you can't just keep using a constant number of ancillary qubits and expect to be able to measure all the possible logical subspaces you might need. It suggests there is an incompressible cost involved in getting those measurements done efficiently.

Lev: So, if we take what they're saying, for codes with a large k, constant overhead ancillas are only going to realize a small fraction of the possible measurements they are allowed to do. That sounds like it puts a real constraint on how much control you can have over which parts of the computation you actually read out.

Kai: Right, so we're talking about this idea that for these sparse stabilizer codes, you need at least squared ancilla qubits if you want to do this surgery in the worst-case scenario <ref:2610.11097#pg1>. It's not just some small constant overhead; it scales with the dimension of the code structure, k.

Mira: And they frame this by looking at what constitutes addressability—that is, how well you can exactly prescribe which degrees of freedom you are reading out through a set of allowed measurements, which they call F. They establish a lower bound for the number of ancilla qubits N based on the size of this set F, stating that N at least F (n) (eight) <ref:2610.11097#pg2>.

Lev: That relationship between F and the required ancilla qubits is what's interesting. It links the complexity of controlling your measurement choices to how much space you have to spare for ancillas. If F gets big, you need more resources.

Kai: And they show that by considering a specific set F' of all k/two-dimensional subspaces of L X, which are guaranteed to commute with a chosen polarization, they can prove that this bound leads to k squared omega (n) (three) <ref:2610.11097#pg2>. That's what drives the main result.

Mira: So, the core message is that unless you allow for a space-time tradeoff—meaning you increase the number of rounds of surgery instead of reducing the space overhead—you are going to be limited in how much measurement control you can achieve with a fixed amount of ancilla qubits for large k codes.

Lev: And they point out that this overhead is even present even when you're only measuring subspaces that are exactly k/two-dimensional, which really tightens the constraint <ref:2610.11097#pg1>. This suggests a fundamental limit on the efficiency of this measurement technique for these codes under these conditions.

Conclusion: Kai: So, thinking about "A lower bound on the overhead of addressable surgery on sparse stabiliser codes," what this paper really tells us is that you can't have perfect control over every measurement you want to make without paying a significant price in ancillary qubits, especially when dealing with sparse stabilizer codes and large k.

Mira: I think the authors are pointing toward a real space-time tradeoff. It suggests that if we want to reduce the number of ancilla qubits needed, we have to be willing to run more rounds of surgery or limit how many logicals you measure at each step.

Lev: From what I've seen in related work, this reinforces the idea that getting low-overhead measurements isn't just about finding a clever circuit; it's about managing a trade-off between space and time in the measurement process itself.

Kai: And for practical quantum computing, this means that for codes where k is large, if you are aiming for constant overhead ancillas, you might only be able to realize a limited set of possible measurements instead of all the ones theoretically allowed.

Mira: It’s important to remember that this result specifically applies to sparse stabiliser codes and relies on specific sparsity conditions for the maps involved, like omega-sparse maps. It doesn't necessarily mean that lattice surgery is useless; it just sets a hard wall on how efficient we can be with the ancilla resources under these constraints.

Lev: And one limitation they mention is that this overhead bound occurs even when you are only measuring subspaces of dimension exactly k/two which means the constraint isn't just about the dimension of what you measure, but the structure of those measurements <ref:2610.11097#pg1>.

Kai: So, in simple terms, for large k codes, constant overhead ancillas simply won't give you full addressability across all measurement possibilities unless you are willing to increase your surgery rounds significantly. That’s what this paper is showing us about the resource cost of precise logical control.

quant-ph

Submitted: 2026-10-08

Updated: 2026-10-09

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 76/100

The gist: The gist: Performing lattice surgery on sparse stabiliser codes with sparse ancillas requires an overhead of at least ˜ k squared ancillary qubits in the worst case, which implies that for codes

Key concepts

Lattice Surgery: This is a technique used to perform logical measurements on quantum codes by embedding the code's structure into a larger symplectic complex. It aims to reduce the operational costs associated with traditional measurement schemes, potentially leading to low-overhead measurements for various quantum codes.
Ancilla Qubits (N⋆): These are extra qubits needed during the surgery process to perform the required logical measurements. The paper shows that for sparse stabiliser codes, the minimum number of ancilla qubits needed is at least Omega(k^2), which is a significant overhead.
Addressability: This refers to the control over which specific degrees of freedom (logicals) can be read out during the surgery process. The paper shows that as the set of allowed measurements F becomes larger (more addressable), the required number of ancilla qubits grows, indicating a space cost.
Sparse Stabiliser Codes: These are quantum codes defined by a set of stabilisers. They are characterized by having a specific structure related to their stabilizers, and the paper focuses on codes where these stabilisers are sparse, which is crucial for deriving the Omega(k^2) lower bound.

Terminology

Addressability — 2× in this paper · explained in 1 episode
Ancilla Qubits — 1× in this paper · explained in 1 episode
Ancillary Qubits — 1× in this paper · explained in 1 episode
No-Go Theorem — 1× in this paper · explained in 2 episodes

Summary

The gist: Performing lattice surgery on sparse stabiliser codes with sparse ancillas requires an overhead of at least ˜ k squared ancillary qubits in the worst case, which implies that for codes with large k, constant overhead ancillas can only realize a small fraction of possible measurements

Background and Motivation

The prospect of practical quantum computers necessitates the ability to record computation outcomes reliably despite noise, which is a challenge in quantum error correction when performing logical measurements. Early methods like Shor and Steane schemes suffered from complex state preparation requirements leading to non-trivial space and time overheads. Lattice surgery allows for greatly reducing these operational costs, with progress toward generalized lattice surgery hinting at low-overhead measurements for all QLDPC codes. A crucial modality is parallel surgery, which allows measuring any set of t commuting logicals on an n-qubit QLDPC code using at most N⋆ ≤ O˜(tn) additional ancilla qubits.

The Lower Bound Result

The main contribution of the work is a no-go theorem showing that some measurement incurs an incompressible overhead, specifically N⋆ ≥ omega(˜k 2). For codes with large k, this implies that constant overhead ancillas can only realize a small fraction of possible measurements. In the case where t is proportional to n, Theorem 3 gives the bound omega(˜n 2) ≤ N⋆ ≤ O˜(n 2). More generally, the bound addresses addressability, which is the capacity to exactly prescribe which degrees of freedom are read through a set F of allowed measurements. This control is expressed by Lemma 2, stating that N⋆ ≥ omega log F log(n).

Formal Setup and Definitions

The paper represents a stabiliser code C on n qubits and m stabilisers using a symplectic complex [YB26]. The space ker ˆσ C is called the logicals of C, which are classified by equivalence up to stabilisers, resulting in 2k = dim H1(C) inequivalent logicals. Performing surgery on C involves an instance of a symplectic embedding [YB26], where the complex is XD QD X Z¯D S C P C S¯C Z D QD Z X¯D p p T. A map ∂ is defined as ω-sparse if both its row and column weight are upper bounded by ω. Definition 1 describes the complex measuring the logical subspace l = g ⊂ H1(C).

Lemma and Theorem

Lemma 2 provides a lower bound on the number of ancilla qubits N⋆ based on a set F of measured subspaces. Lemma 5 establishes a lower bound for the number of r-dimensional subspaces of F l squared as 2r(l-r). Theorem 3 addresses addressability, stating that if F is the set of all possible measurements and the ancilla complex satisfies certain sparsity conditions, then N⋆ ≥ omega k squared ω log(n). This bound is achieved by considering the set F' of all k/2-dimensional subspaces of LX, which are guaranteed to commute with a chosen polarization.

Auxiliary Lemmas

Lemma 4 bounds the number of ω-sparse matrices by showing there are at most (1 + s)ωt ω-sparse matrices of dimension F s×t squared. Lemma 5 provides the lower bound on the number of r-dimensional subspaces of F l squared as 2r(l−r). These auxiliary results are essential for deriving the main lower bounds.

Conclusion on Trade-off

The result points towards a space-time tradeoff, indicating that to reduce space overhead, one must limit the number of logicals measured at every surgery operation and thus increase the number of rounds of surgery needed. The overhead is shown to occur even when only measuring subspaces of dimension exactly k/2.

--- Page 1 ---

A lower bound on the overhead of surgery on sparse stabiliser codes

Nouedyn Baspin ´

Iceberg Quantum

Sydney, Australia

nouedyn@iceberg-quantum.comWe show that performing lattice surgery on sparse stabiliser codes with sparse ancillas requires omega(˜k 2) ancillary qubits in the worst case. As a result, for codes with large k, constant overhead ancillas can only realise a small fraction of possible measurements.

The prospect of practical quantum computers requires the ability to record the outcome of a computation, once completed. However, the process of reading information out of a computer is made challenging by the presence of noise; as measurements used to estimate the computational state can be irreversibly corrupted. In quantum error correction, this problem corresponds to performing a reliable logical measurement on an encoded state. Early efforts to solve this issue led to the Shor and the Steane measurement schemes [Sho96, Ste97, HJOY23]; but with both suffering from complex statepreparation requirements, they incur non-trivial space and time overheads.

Lattice surgery [BMD09, HFDM12], allows for greatly reducing these operational costs. While originally only applicable to surface codes, then topological codes, the progress toward generalised lattice surgery [CKBB22, WY24, CHWY25] seems to hint at the possibility of low overhead measurements for all QLDPC codes.

A crucial modality in the realisation of surgery, is whether multiple logicals operators can be measured simultaneously, which is often referred to as parallel surgery [CHWY25]. A construction of parallel surgery is given in [CHWY25], which allows for measuring any set of t commuting logicals on an n-qubit QLDPC code, using at most N⋆ ≤ O˜(tn) (1) additional ancilla qubits. The main contribution of our work is a no-go theorem showing that some measurement incur an incompressible overhead, i.e N⋆ ≥ omega(˜k 2) (2).

In particular, Eq. (1) is almost tight for constant rate codes. In which case, taking t ∝ n, Theorem 3 gives: omega(˜n 2) ≤ N⋆ ≤ O˜(n 2) (3).

In full generality, our bound targets addressability, i.e. the capacity to exactly prescribe which degrees of freedom are read. Such a high degree of control can be expressed as the (large) set F of all the measurements allowed by the surgery scheme. Our result, Lemma 2, then reads N⋆ ≥ omega log F log(n).

The larger F, or the more addressable, the worse is the space cost. We note that this bound seems to point towards a space-time tradeoff: in order to reduce the space overhead, one has to limit the number of logicals that can be measured at every surgery operation (or logical time step), and therefore increase the number of rounds of surgery needed.

For example, the work of [CI26] provides an almostlinear overhead surgery construction for a logical subspace, provided the existence of a suitable subcode. As a consequence ofTheorem 3, these subcodes happen to be in limited supply, at least for codes satisfying k ≫ √n; and thus this method does not generically provide addressability.

I. LOWER BOUND

We represent a stabiliser code C on n qubits and m stabilisers as a symplectic complex [YB26]: C = S C σ C / C → P C σˆ C / C → S¯C (5)With P C ∼= F 2n / 2 representing to the space of physical Pauli operators, while S C ∼= S¯C ∼= F m / 2 represent the stabilisers. We also use the following grading C = C2 → C1 → C0 (6)The space ker ˆσ C is called the logicals of C, which are classified by equivalence up to stabilisers. The code C has then 2k = dim H1(C) inequivalent logicals.

Performing surgery on C, with a CSS ancilla D = XD → QD X → Z¯D, and associated grading D = D1 → D0 → D−1 can then be formally expressed as an instance of a symplectic embedding [YB26]: XD QD X Z¯D S C P C S¯C Z / D QD Z X¯D p p T (7)Where (g, h) is a chain map, p is a defect map satisfying ggˆ = ∂ D T p + p T∂ D, and H0(D) = 0. We say that a map ∂ is ω-sparse if both its row and column weight are upper bounded by ω.

Improvements for AI systems

No-Go Theorem for Incompressible Overhead: The paper proves that some measurement incur an incompressible overhead by showing that for parallel surgery, N⋆ ≥ omega(˜ k2) (2). This means current methods using constant overhead ancillas can only realise a small fraction of possible measurements.
Addressability Trade-off Management: For practical quantum error correction, the system can be improved by understanding the inherent space-time tradeoff: in order to reduce the space overhead, one has to limit the number of logicals that can be measured at every surgery operation (or logical time step), and therefore increase the number of rounds of surgery needed.
Optimized Measurement Scheme for Sparse Codes: The system can utilize the bound derived in Lemma 2, which states N⋆ ≥ omega log F / ω log(n) (15), to determine the minimum required ancillary qubits based on the set of measurements F that must be performed.
Guaranteed Measurement Coverage for Specific Subspaces: By exploiting Theorem 3, the improved system can guarantee measurement coverage for a specific subset of logical operators: We can guarantee that all the logicals in a given l ∈ F do commute and therefore constitute valid measurements when measuring all subspaces of dimension exactly k/2.
Resource Allocation for Parallel Surgery: When implementing parallel surgery, the system can use the construction from [CHWY25] to measure any set of t commuting logicals on an n-qubit QLDPC code, using at most N⋆ ≤ O˜(tn) (1) additional ancilla qubits. This allows for controlled execution of multiple logical measurements simultaneously.