Quantum List Recovery and Decoding: Achievability and Limitations

1 Introduction

• The quantum Singleton bound limits correctable erasures to (1 − R)/2, while exact adversarial decoding has radius at most (1 − R)/4 [BGG24].The gap motivates studying approximate quantum error correction and list-based decoding near the Singleton radius.Source: §1 · p. 3
• Classical list decoding and recovery have developed bounds for folded Reed–Solomon and random linear codes, including lower bounds whose output-list size grows exponentially in the inverse slack [CZ25] [LS25].The paper asks which such combinatorial bounds transfer to quantum list problems, where the counted objects are logically distinct Pauli errors.Source: §1 · pp. 3–4, §1.1 · p. 4

1.1 Quantum CSS code: Two questions

• For CSS codes, separate X- and Z-sector list recovery can discard paired constraints and enlarge the allowed candidates to a Cartesian product.Moreover, classically distinct candidates may collapse to one logical correction when their difference is a stabilizer.Source: §1.1 · pp. 5–6

1.2 Our contributions

• The paper establishes a pairing lemma that avoids sector-product loss and quotient-aware converses and lower bounds for balanced FQRS and random CSS codes.The lower-bound constructions preserve classical bad-list growth while keeping candidates distinct modulo stabilizers.Source: §1.2 · p. 6

1. Joint achievability without a sector-product loss (to Question 1)

• Coordinate certificates require the specified inequalities to hold for every random word supported on the candidate set.The bounded-support variant restricts this requirement to distributions supported on at most B words.Source: §1 · p. 7
• The pairing lemma combines an X-projection certificate and certificates on each corresponding Z-fiber with coefficient min{δX, δZ}.The same pairing property holds for bounded-support versions of the certificates.Source: §1 · p. 7
• Once one-sector certificates are available, entropy- and remainder-to-list conversions yield joint QLR and QLD bounds without multiplying sectorwise list sizes.This uses the conversions developed by Brakensiek, Chen, Dhar, and Zhang [BCDZ26a].Source: §1 · p. 7
• For FQRS codes, subspace-design structure and entropic and remainder Brascamp–Lieb inequalities provide the required certificates.For random CSS codes, bounded-support certificates are established directly by showing certificate violations require rare structured local collision profiles.Source: §1 · p. 7

2. Quotient-aware generalized Singleton bounds for QLD (to Question 2)

• The converse adapts the classical generalized Singleton projection-and-patching argument, requiring candidates to represent distinct classes modulo the stabilizer.For a CSS code, a quotient-distinct bad list in either marginal quotient can be lifted to a stabilizer-distinct list by fixing the other sector.Source: §2 · p. 7
• The quotient-aware bound constructs L + 1 distinct quotient representatives in a common Hamming ball, provided L + 1 ≤ |C/W|.For balanced scalar CSS codes, the two marginal redundancies equal (1 − R)n/2.Source: §2 · pp. 7–8
• Above the one-sector redundancy, the largest coset list grows exponentially; consequently, subexponential QLD list size near the quantum Singleton radius requires approximate balance.The balance consequence applies to scalar CSS families at radius ρ = (1 − R)/2 − γ.Source: §2 · p. 8
• For FQRS codes, the projection argument must select whole folded registers, and the underlying Reed–Solomon stabilizer subcode's MDS structure makes this possible.A scalar information set may otherwise be scattered across too many registers.Source: §2 · p. 8

3. Quotient-aware lower bounds for QLR (to Question 2)

• The lower-bound goal is to retain the classical ℓ^Θ(R1/γ) list-size scale while ensuring candidates remain distinct modulo the stabilizer.For lower bounds, the construction can be carried out in one sector.Source: §3 · p. 8
• The FQRS construction adapts the diagonal-product grid to produce ℓ⌈R1/γ⌉ stabilizer-distinct candidates at radius (1 − R)/2 − γ.Distinct generator degrees in [d0, k1) prevent the highest-degree term in a nonzero candidate difference from cancelling.Source: §3 · p. 8
• For random CSS codes, starting from a classical rate-R1 bad list of size M = ℓ⌊R1/γ⌋, each fixed nonzero difference lands in the random stabilizer subcode with probability at most 2q^−Rn.A union bound shows all M candidates remain distinct modulo the stabilizer with probability at least 1 − 2M²q^−Rn.Source: §3 · p. 8

1.3 Technical overview

• The pairing lemma removes the QLR sector-product loss: multiplying marginal lists squares the one-sector bound and doubles the exponent constant, while pairing preserves that bound.The joint certificate framework combines paired candidate lists without multiplying the two sector list sizes.Source: §4 · p. 9, §1.3 · p. 10

4. Matching achievability and lower bounds

• For QLD near the Singleton radius, the one-sector remainder conversion gives list size of order 1/γ rather than the 1/γ^2 order from a sector-product argument.The pairing lemma preserves the one-sector certificate coefficient and hence the 1/γ order.Source: §4 · p. 9
• The fixed-list converse and achievability yield an asymptotically tight radius–list-size tradeoff for QLD.The tradeoff combines joint achievability with the quotient-aware generalized Singleton converse.Source: §4 · p. 9
• For both FQRS and balanced random CSS codes, QLR upper and lower bounds match at the exponent scale and QLD bounds at the list-size order; random-CSS achievability holds with high probability.Results are for fixed rate near the Singleton radius; family-specific alphabet, folding, and block-length conditions may differ.Source: Table 1 · p. 9, §4 · p. 9

1.3 Technical overview

• Entropy combines across X and Z through the chain rule, while remainder certificates use a distance interpretation and paired Hamming disagreement across fibers.The X-certificate controls the representative contribution; Z-fiber certificates control residual mass conditioned on X.Source: §1.3 · p. 10
• The quotient-aware generalized Singleton argument selects L+1 codewords in one projection fiber while ensuring they represent distinct stabilizer quotient classes, then patches coordinates into a common ball.Choosing the projection to contain an information set of the stabilizer subcode prevents distinct codewords from collapsing within a coset.Source: §1.3 · pp. 10–11
• The FQRS QLR lower-bound construction adapts a diagonal product of candidate choices by separating generator degrees, so nonzero differences stay outside the stabilizer subcode.The construction uses b = ceil(R1/γ) and places generator degrees in [d0, k1) while meeting the list-recovery agreement condition.Source: §1.3 · pp. 11–12

2.1 CSS codes, quantum list problems, and quotient reduction

• CSS QLD and QLR count pairwise stabilizer-distinct Pauli errors with a common syndrome; translating by a reference identifies candidates with distinct logical-quotient cosets while preserving disagreement.QLD is the special case of QLR with local-list size ℓ = 1.Source: §2.1 · pp. 13–14

2.2.1 Balanced FQRS codes

• Balanced FQRS codes use nested component codes with rate R1, and their logical messages occupy the polynomial coefficient band [d0, k1).The construction has C2⊥ ⊆ C1, with both component dimensions equal to R1sn.Source: §2.2.1 · p. 14

2.2.2 Balanced random CSS codes

• The balanced random CSS ensemble samples an ordered independent family to form nested component codes, producing a rate-R code whose two component spaces are marginally uniform.Both component dimensions are R1n.Source: §2.2.2 · p. 15

2.3 Subspace designs and Brascamp–Lieb inequalities

• For folded Reed–Solomon codes, affine containment and coordinate-kernel subspace designs supply discrete Brascamp–Lieb entropy or remainder bounds for list recovery and fixed-list decoding.Uniform candidate distributions turn entropy into log list size; the entropy and remainder certificate conversions yield average-radius guarantees, which imply standard-radius guarantees.Source: §2.3 · pp. 15–17
• For folded Reed–Solomon list recovery, s ≥ 16ℓ/ε² gives ε/3-slacked (4ℓ/ε)-subspace designability and radius 1 − Rc − ε; average-radius recovery also follows when s ≥ L(1 + 3Rc/ε).The first condition gives list size L; the second gives average-radius (1 − Rc − ε, ℓ, L)-list recovery.Source: §2.3 · p. 16
• For every ρ < L/(L+1)δ, the remainder calculation gives average-radius (ρ, L)-list decoding, and hence standard-radius list decoding [BCDZ26a, Theorem 5.2].The condition is that every distribution supported on at most L + 1 candidates satisfies the stated rank inequality.Source: §2.3 · p. 17
• Every sufficiently large rate-Rc Fq-linear code has local lists of size at most ℓ containing at least M = ℓ^floor(Rc/ε) codewords within distance (1 − Rc − ε)n, so it is not (1 − Rc − ε, ℓ, M − 1)-list recoverable [LS25, Theorem 12].This holds for 0 < ε < 1 − Rc and 2 ≤ ℓ ≤ q.Source: §2.3 · p. 17

• For entropy, conditioning on X lets the proof apply the X certificate and then the Z-fiber certificates before averaging.The proof uses that conditioning on X can only reduce entropy.Source: §3 · p. 18
• Remainder lacks an additive chain rule, so the proof decomposes mass by X-fibers and patches centers to control paired disagreement without double-counting coordinates.The resulting fiber bound combines the representative and residual masses, and the joint remainder is controlled by the X certificate and fiberwise Z certificates.Source: §3 · pp. 18, 20, 21
• The bounded-support corollary applies when the X-projection and each conditional Z-fiber have bounded support, yielding joint entropy or remainder certificates.For output-list bounds, certificates are needed only for distributions supported on boundedly many words, since one rules out a bad list of L + 1 candidates.Source: §3 · pp. 17, 21
• Joint X/Z certificates retain coefficient min{δX, δZ}, avoiding the product loss of separate sectorwise list-size bounds.The pairing lemma combines an X-projection certificate with certificates for each conditional Z-fiber.Source: §3 · pp. 17, 21
• The one-sector inputs come from subspace-design Brascamp–Lieb inequalities for subspace-designable codes or high-probability certificates for random linear codes.Once those inputs hold, the pairing lemma gives the joint certificate with the smaller one-sector coefficient.Source: §3 · p. 21

4 Coset Singleton converse for QLD

• A stabilizer-distinct bad list in one sector lifts to a joint CSS list of the same size, preserving disagreement and average-radius bounds.Taking ℓ=1 gives QLD.Source: §4 · pp. 21–22

4.1 Coset Singleton bound and its CSS consequences (unfolded case)

• The coset generalized Singleton lemma uses projection and patching to force L+1 representatives of distinct cosets inside a Hamming ball.The projection is injective on the subspace being quotiented, so candidates in one projection fiber represent distinct cosets.Source: §4.1 · pp. 22–23
• Once the radius exceeds the code redundancy fraction, the forced coset list grows exponentially in the excess, up to the quotient size.At radius 1 − Rc + ε, the stated lower bound is min{q^(εn+O(1)), |C/W|}.Source: §4.1 · pp. 23–24
• Near the quantum Singleton radius, subexponential QLD lists require scalar CSS families to be approximately balanced.The redundancy imbalance is bounded by 2γn + 2 log_q Ln + 2 when ρ = (1 − R)/2 − γ.Source: §4.1 · p. 24
• For balanced CSS codes, any fixed QLD list budget L requires L = Ω((1 − R)/γ) as γ approaches zero, for both standard- and average-radius QLD.The construction gives a bad list of size L+1 at radius (1 − R)/2 + O(1/n).Source: §4.1 · pp. 24–25

4.2 Folded quotients

• For folded quotients, projection-and-patching gives a conditional bound: enough whole registers must determine W while leaving a fiber with at least L+1 codewords.An Fq-information set may be scattered across folded registers, so the scalar-case compatibility is not automatic; the paper applies the conditional bound to FQRS codes.Source: §4.2 · pp. 25–26

5.1 Achievability: Classical BL inputs

• If s ≥ 16ℓ/γ^2, the stated QLR guarantee is standard-radius; if s ≥ L(1 + 3R1/γ), it is average-radius.Both guarantees have radius (1 − R)/2 − γ.Source: §5.1 · p. 27
• For FQRS QLR achievability, the pairing lemma carries one-sector entropy certificates to paired X/Z candidates without multiplying the sector list sizes.Subspace-design structure supplies the one-sector certificates for the relevant candidate sets.Source: §5.1 · pp. 26–27
• The QLD achievability argument uses remainder certificates on one-sector candidate sets and applies the pairing lemma to the joint candidates.For L+1 paired candidates, each one-sector projection or fiber has affine message span of dimension at most L.Source: §5.1 · p. 27

5.2.1 QLR: Diagonal-product grid construction

• The QLR lower-bound construction adapts Chen and Zhang’s folded-RS construction [CZ25] with generators of distinct degrees, preventing cancellation and preserving stabilizer distinctness.The resulting ℓ^b candidates form one radius-ρ instance and yield both standard- and average-radius lower bounds when the construction’s integer conditions hold.Source: §5.2.1 · pp. 27, 30
• The construction’s degree conditions place generators above the stabilizer cutoff while keeping them inside C1, so nonzero candidate differences remain outside the stabilizer.The grid contains ℓ^b candidates in the same list-recovery instance.Source: §5.2.1 · pp. 28–30

5.2.2 QLD lower bound: Coset GSB

• Whenever L + 1 ≤ (qs)Rn, Q is neither standard- nor average-radius (ρ, L)-QLD for any ρ ≥ ρL.Source: §5.2.2 · p. 31

5.3 Matching list-size scales

• The FQRS bounds match the QLR list-size exponent in both standard- and average-radius settings under their respective folding conditions.The upper bound inherits the classical folded-RS exponent; pairing avoids the sector-product argument’s factor-two loss in the exponent.Source: §5.3 · p. 31
• For QLD near the Singleton radius, the stated budget is L = ⌈(1 − R)/γ⌉, with both standard- and average-radius statements under the given folding condition.The corollary gives the corresponding near-Singleton matching result for sufficiently large admissible blocklengths.Source: §5.3 · p. 31

6.1 Achievability: Collision patterns and random-linear certificates

• With probability 1-o(1), random CSS codes achieve standard- and average-radius QLR at radius (1-R)/2-γ, after both components satisfy entropy certificates and bounded-support pairing combines their candidates.The theorem assumes fixed R and ℓ≥2, with field-size and blocklength conditions specified in the statement.Source: §6.1 · p. 35

6.3 Matching list-size scales

• Random CSS codes achieve average-radius (ρ,L)-QLD with high probability for ρ<L/(L+1)(1-R1-ε), under the theorem’s field-size and blocklength conditions.The matching-scale analysis compares this achievability threshold with deterministic bad lists of size m+1 at radius m/(m+1)·(1-R)/2+O(1/n).Source: §6.1 · p. 35, §6.3 · p. 37

6.2.1 QLR lower bound: Dimension count

• With probability 1-o(1), no random CSS code is standard- or average-radius (ρ, ℓ, M-1)-QLR at ρ=(1-R)/2-γ, where M=ℓ^floor(R1/γ).The lower-bound proof starts with a classical bad list and shows its candidates remain pairwise distinct modulo the stabilizer with high probability.Source: §6.2.1 · pp. 35–36

6.2.2 QLD lower bound: Coset GSB

• Every balanced realization fails standard- and average-radius (ρ,L)-QLD for radii at or above the coset Singleton threshold ρL, whenever L+1≤q^Rn.The converse applies the scalar coset generalized Singleton bound to either quotient component.Source: §6.2.2 · p. 36

6.3 Matching list-size scales

• The QLR achievability and lower-bound results match in their near-Singleton list-size scale, for both standard- and average-radius settings, with high probability.The achievability theorem applies at radius (1-R)/2-γ; the lower bound rules out lists of size M-1 for M=ℓ^floor(R1/γ).Source: §6.1 · p. 35, §6.2.1 · p. 35, §6.3 · p. 36

AI Disclosure

• The research project began around January 2026, and the authors formulated its overall direction and questions.Source: AI Disclosure · p. 37
• The authors used ChatGPT 5 Pro, ChatGPT 6 Astra, and Claude Fable as research assistants and for editorial assistance.They describe extensive iterative interactions over several months.Source: AI Disclosure · p. 37
• The authors report substantial human effort in developing and presenting the work, take full responsibility, and independently verified its mathematical claims, proofs, and references.Source: AI Disclosure · p. 37