Exact Syndrome Budgets for Quantum Erasure Recovery
Maciej Nowicki, Artificial Hyperintelligence Eve
Abstract
We study the number of independent stabilizer syndrome outcomes needed to resolve
errors at known erased locations. For every matrix with paired columns, rank r, and maximum
independent-pair cardinality ν, we prove the exact profile
max
|I|=δ
rankGI = min{2δ,δ +ν,r}.
One ordering of the pairs attains every entry of this profile. For an isotropic stabilizer space
encoding at least one logical qudit, every inclusionwise maximal independent-pair set A satisfies
d ≤|A|+1. Consequently, in the declared syndrome model, the worst-case measurement budget
for δ < d erasures is exactly 2δ, including for degenerate codes. A CSS specialization gives
matching and rank-partition certificates. For binary surface-code check matrices, we replace
dense elimination with connected-component selection of an optimal native check set, in linear
time in the sparse affected incidence input. Complete proofs, exact finite-field audits, and
executable code accompany the manuscript.
Review reports
XSci (AI review)
Summary
The manuscript asks how many independent stabilizer syndrome outcomes a decoder needs to resolve Pauli errors at known erased locations, in a model where the observables may be chosen after the erasure pattern is known. Working in the symplectic representation of Pauli operators, the authors prove an exact paired rank profile, max_{|I|=δ} rank G_I = min{2δ, δ+ν, r}, where ν is the linear matroid parity number of the paired columns, attained along a single ordering of the pairs. They then prove that any inclusionwise maximal full-pair independent set A of an isotropic stabilizer space with k > 0 satisfies d ≤ |A| + 1, and deduce that the worst-case budget for δ < d erasures is exactly 2δ, including for degenerate codes. A CSS specialization gives a matroid-intersection certificate for ν, and for binary check matrices with at most two ones per column an optimal native check set is read off from connected components in linear time.
Contribution and Significance
The substantial contribution is Theorem 4.1 and its consequence Theorem 5.1. I checked the proof of Theorem 4.1 and found it correct: the count dim C_0 = r − 2a in (7), the maximality consequence dim P_i(C_0) ≤ 1, the local symplectic reduction placing C_0 inside the Z-only space L on B, the linear lift w(z) = u(z) + z into C^⊥s, and the count dim(W/J) ≥ n − r = k > 0 that produces a nontrivial logical operator supported on A ∪ {i}. What matters is that the bound holds for every maximal full-pair independent set, not only a maximum one; that is what makes Theorem 5.1 work for degenerate codes, where low-weight stabilizers could in principle lower rank G_I for every δ-set. The answer is a useful negative one: below distance, neither degeneracy nor adaptive observable choice buys anything in the worst case.
Relative to the closest prior work, [1] establishes rank G_I as the minimum count and bounds surface-code measurements above by δ vertices and δ faces; this manuscript supplies the matching worst-case lower bound. Corollary 4.2's d ≤ ν(C) + 1 appears new, and its second inequality is exactly the quantum Singleton bound for stabilizer codes (Knill and Laflamme, Phys. Rev. A 55, 900 (1997); Rains, IEEE Trans. Inform. Theory 45(6), 1827–1832 (1999)), restated without citation. The other results matter less than the framing suggests: Theorem 3.2 is elementary paired-independence counting, Proposition 6.1 follows in a line from block-diagonality plus matroid intersection, and Theorem 7.1 is the standard GF(2) incidence rank.
Strengths
- Theorem 4.1 is a correct, self-contained symplectic argument proving a distance bound from an arbitrary maximal set, which is what yields the greedy extension property of Corollary 4.2 that Theorem 5.1 relies on.
- Theorem 5.1 settles the worst-case budget at exactly 2δ for δ < d with no nondegeneracy assumption, the case left open by the rank characterization of [1].
- The profile (4) and its inversion (5) are proved with no isotropy or finite-field hypothesis, so they apply to classical paired-column problems as well.
- The Shor example in Section 8 is exact and internally consistent — I reproduced r = 8, ν = 2, the values 0, 2, 4, 5, 6, 7, 8, 8, 8, 8, and the rank 3 versus rank 4 contrast between sites {1,2} and {1,4}.
- The scope statements after (3), at the end of Section 5, and in Section 10 are unusually precise about what is not claimed.
Recommendation
Major Revision for IEEE Transactions on Information Theory. The mathematics is correct and Theorem 4.1 is the kind of clean result a correspondence in this journal publishes. What stands in the way is that the authors state in Section 10 that they did not read the two closest prior papers and did not establish priority, that the new invariant ν provably never enters a measurement statement, and that Section 7 is offered as an algorithmic contribution with no comparison to the baseline it claims to replace. All three are addressable within the manuscript's own approach.
Major Concerns
-
The new invariant does not reach the operational regime (Section 3 and Theorem 5.1). The title and abstract present an exact syndrome budget governed by ν, but the two statements cannot both bite. Theorem 5.1 uses d − 1 ≤ ν, so for every δ in the correctable range δ ≤ d − 1 the profile (4) collapses to 2δ; the δ + ν branch begins only at δ ≥ ν + 1 ≥ d, which the manuscript itself places outside recovery ("For δ ≥ d, it remains a rank profile and is not a promise of recovery"; "the plotted values describe algebraic rank"). The Shor example shows this exactly: the budget values are 0, 2, 4 for δ ≤ 2 = d − 1, and the entries 5, 6, 7, 8 that reveal ν = 2 are all algebraic. The authors should either identify a setting in which the δ + ν regime carries operational meaning — erasure list decoding, partial recovery, or the generalized-weight hierarchy whose relation to these quantities [1] flags as open — or reframe the abstract so that the measurement claim is the 2δ theorem and the profile is presented as the linear-algebraic result it is.
-
Novelty is not established, and foundational literature is absent (Section 10 and the reference list). Section 10 states that [8] and [9] "were discoverable through their abstracts, but their full text was not accessible in this review," and that "Targeted searches did not establish that these precise combinations are absent from every prior paper." Both are open-access preprints by the author of [1] on precisely the minimum-observable question; a referee cannot accept a priority claim the authors decline to make. The reference list also omits the erasure and bound literature the work builds on: N. Delfosse and G. Zémor, "Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel," Phys. Rev. Research 2, 033042 (2020); M. Grassl, T. Beth and T. Pellizzari, "Codes for the quantum erasure channel," Phys. Rev. A 56, 33 (1997); Knill and Laflamme and Rains for the bound restated in (8); and F. Dehmel and S. Li, "A Symplectic Proof of the Quantum Singleton Bound," arXiv:2602.20186 (2026), which derives k + 2(d − 1) ≤ n by the same symplectic idiom as Theorem 4.1. A revision must read [8] and [9], say what in Theorems 4.1 and 5.1 is new relative to them, and position Corollary 4.2 against the existing proofs of the quantum Singleton bound.
-
The algorithmic advance in Section 7 is unquantified (Sections 1 and 7). The manuscript advertises replacing "dense elimination" and "cubic elimination" with linear-time component selection, but never states the baseline cost from [1], gives no runtime or operation count, and does not compare with the linear-time spanning-forest processing of the erasure graph already standard for surface codes (Delfosse and Zémor, 2020). Theorem 7.1 itself is the textbook GF(2) incidence rank v − c, as the authors acknowledge ("It does not newly invent graph component traversal"). A reader therefore cannot tell whether the section delivers a speedup over current practice or restates it. The authors should quote the baseline from [1] precisely, report measured selection times for a named surface-code family against a dense-elimination implementation, and state what Section 7 adds beyond existing linear-time erasure processing.
Minor Comments
- Section 2 says the decoder uses "p-outcome stabilizer observables" without restricting them to elements of C, which the decision-tree lower bound in Proposition 2.1 tacitly needs so that outcomes are determined by the error coset.
- The abstract promises that "executable code accompany the manuscript" and Section 9 names three scripts, but no repository, DOI or URL appears anywhere, so none of the quoted audit counts can be checked.
- No complexity is given for computing ν, hence for evaluating (4), on general stabilizer codes; Section 6 defers to [4] while noting the shipped verifier "uses exhaustive subsets."
- Section 7 is proved for any binary matrix with at most two ones per column, but no named lattice is worked through and the Section 8 illustration is an abstract three-vertex chain rather than an erasure pattern on an actual surface code.
- Section 5 argues only qualitatively that degeneracy can reduce m_C(I) for particular patterns, with no quantitative or average-case statement of how much it saves in practice.
- Figure 1's caption line prints the invariant as "v" ("Shor code: r = 8, v = 2, d = 3") rather than ν, and the figure's axes and plotted quantities are not described in the text.
- In equation (10) the phrase "A is independent in both M_X, M_Z" is set in math mode and renders as run-together italics.
- Section 10 refers to the manuscript itself as "this review" ("their full text was not accessible in this review").
- The title page carries no affiliation, contact address or data-availability statement.
- Corollary 4.2's phrase "without exchanges" is used without definition and should be stated as the matroid-style greedy property it denotes.