Quantum List Recovery and Decoding: Achievability and Limitations
Abstract
Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the X- and Z-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let R∈(0,1) be the quantum rate and R1=(1+R)/2 the common component rate. As the radius ρ=(1−R)/2−γ approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, L⋆QLR = ℓΘ(R1/γ), L⋆QLD = Θ ((1−R)/γ) (γ↓0). The asymptotically exact QLD radius tradeoff is ρL⋆ = L/(L+1)(1−R)/2. These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint X/Z candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.
Related
- Combinatorial limitations of list-decoding Reed-Solomon codes
- Bounds and Limitations on Codes Achieving List Recovery Capacity
- Achievability of CSS codes performance limits over Pauli channels under separate ML decoding with bounded graphical complexity
- Algorithmic List Decoding of Reed-Solomon Codes up to Capacity
- Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps
BibTeX
@misc{jeronimo2026quantum,
title = {{Quantum List Recovery and Decoding: Achievability and Limitations}},
author = {Fernando Granha Jeronimo and Xiaojuan Ma},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.40262},
eprint = {2609.40262},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.40262},
}
RIS
TY - UNPB
TI - Quantum List Recovery and Decoding: Achievability and Limitations
AU - Fernando Granha Jeronimo
AU - Xiaojuan Ma
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.40262
UR - https://arxiv.org/abs/2609.40262
AB - Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the X- and Z-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let R∈(0,1) be the quantum rate and R_1=(1+R)/2 the common component rate. As the radius ρ=(1−R)/2−γ approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, L^⋆_QLR = ℓ^Θ(R_1/γ), L^⋆_QLD = Θ ((1−R)/γ) (γ↓0). The asymptotically exact QLD radius tradeoff is ρ_L^⋆ = L/(L+1)(1−R)/2. These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint X/Z candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.
ER -