arXiv:2609.40262
Quantum List Recovery and Decoding: Achievability and Limitations
Fernando Granha Jeronimo, Xiaojuan Ma
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\in(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^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ ρ_L^\star = \frac{L}{L+1}\frac{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.
AI Summary
Quantum list decoding (QLD) and list recovery (QLR) count logically distinct Pauli corrections compatible with a syndrome and error constraints. This paper asks whether CSS codes can inherit classical list-size bounds without multiplying the $X$- and $Z$-sector lists, and whether classical lower bounds survive identification modulo stabilizers. For balanced folded quantum Reed–Solomon (FQRS) codes and balanced random CSS codes, it gives matching asymptotic list-size scales at radius $\rho=(1-R)/2-\gamma$. Writing $R_1=(1+R)/2$, the bounds are $L^\star_{\mathrm{QLR}}=\ell^{\Theta(R_1/\gamma)}$ for fixed $\ell\ge2$ and $L^\star_{\mathrm{QLD}}=\Theta((1-R)/\gamma)$. The asymptotically optimal fixed-list QLD radius is $\rho_L^\star=\frac{L}{L+1}\frac{1-R}{2}$. Corresponding results hold for average-radius decoding and recovery. Achievability uses entropy and remainder coordinate inequalities, combined through a pairing lemma that preserves the one-sector coefficient. FQRS certificates follow from classical subspace-design and Brascamp–Lieb inputs; random-code certificates follow by excluding collision profiles. Converses use projection and patching with an information set for the stabilizer subcode. QLR lower bounds use degree-separated polynomial generators for FQRS and a probabilistic stabilizer-quotient survival argument for random CSS. A further scalar-CSS converse requires approximate balance near the Singleton radius when lists are subexponential. The results are combinatorial, with family-specific alphabet, folding, and block-length requirements. Random-CSS achievability requires large alphabets and holds with high probability; FQRS bounds require sufficient folding. The folded converse needs an additional register-information condition, verified here for FQRS. QLR bounds match the exponent scale, not its exact constant.
we used multiple versions of ChatGPT 5 Pro, ChatGPT 6 Astra, and Claude Fable as research assistants through extensive iterative interactions, as well as for editorial assistance.
Error found: The abstract omits the folding and alphabet conditions under which the body proves its matching list-size bounds. The exact fixed-list QLD radius is established as a limiting tradeoff with increasing folding or alphabet, rather than as a general blocklength-asymptotic threshold at fixed folding and alphabet.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.