Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2601.09786 · IEEE International Symposium on Information Theory (ISIT)

Zero-Error List Decoding for Classical-Quantum Channels

Marco Dalai, Filippo Girardi, Ludovico Lami

quant-phcs.ITmath-phSubmitted Jan 14, 2026• Announced Jan 16, 2026• 2 citations
v1 · Jan 14, 2026v2 · Apr 16, 2026
arXivHTMLPDF

Abstract

The aim of this work is to study the zero-error capacity of pure-state classical-quantum channels in the setting of list decoding. We provide an achievability bound for list-size two and a converse bound holding for every fixed list size. The two bounds coincide for channels whose pairwise absolute state overlaps form a positive semi-definite matrix. Finally, we discuss a remarkable peculiarity of the classical-quantum case: differently from the fully classical setting, the rate at which the sphere-packing bound diverges might not be achievable by zero-error list codes, even when we take the limit of fixed but arbitrarily large list size.

Comments
5+1 pages, 1 figure

Related papers

SPHERE PACKING AND ZERO-RATE BOUNDS TO THE RELIABILITY OF CLASSICAL-QUANTUM CHANNELS

Marco Dalai

In this paper, the sphere packing bound of Fano, Shannon, Gal- lager and Berlekamp and the zero-rate bound of Berlekamp are extended to general classical-quantum channels. The upper bound for the reliability func- tion obtained from the sphere packing coincides at high rates, for the case of pure state channels, with a lower bound derived by Burnashev and Holevo (21). Thus, for pure state channels, the reliability function at high rates is now ex- actly determined. For the general case, the obtained upper bound expression at high rates was conjectured to represent also a lower bound to the reliability function, but a complete proof has not been obtained yet. Finally, the obtained zero-rate upper bound to the reliability function of a general classical-quantum channel with no zero-error capacity coincides with a lower bound obtained by Holevo, thus determining the exact expression.

•Jan 25, 2012•2 citations

Lower Bounds on the Probability of Error for Classical and Classical-Quantum Channels

Marco Dalai

In this paper, lower bounds on error probability in coding for discrete classical and classical-quantum channels are studied. The contribution of the paper goes in two main directions: 1) extending classical bounds of Shannon to classical-quantum channels, and 2) proposing a new framework for lower bounding the probability of error of channels with a zero-error capacity in the low rate region. The relation between these two problems is revealed by showing that Lovász' bound on zero-error capacity emerges as a natural consequence of the sphere packing bound once we move to the more general context of classical-quantum channels. A variation of Lovász' bound is then derived to lower bound the probability of error in the low rate region by means of auxiliary channels. As a result of this study, connections between the Lovász theta function, the expurgated bound of Gallager, the cutoff rate of a classical channel, and the sphere packing bound for classical-quantum channels are established.

arXiv:1201.5411•IEEE Transactions on Information Theory•Sep 26, 2013•71 citations

Quantum Sphere-Packing Bounds With Polynomial Prefactors

Hao-Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden-Thompson inequality, reaffirming that Dalai's expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai's prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(logn/n), indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.

arXiv:1704.05703•IEEE Transactions on Information Theory•Jan 8, 2019•53 citations

Sphere-packing bound for classical-quantum channels

Hao–Chung Cheng, Min-Hsiu Hsieh, Marco Tomamichel

We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.

IEEE Information Theory Workshop (ITW)•Nov 1, 2017•1 citation

Semidefinite Programming Strong Converse Bounds for Classical Capacity

Xin Wang, Wei Dong Xie, Runyao Duan

We investigate the classical communication over quantum channels when assisted by no-signaling and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmission rate and the one-shot E-error capacity are formalized as semidefinite programs (SDPs). Based on this, we obtain improved SDP finite blocklength converse bounds of general quantum channels for entanglement-assisted codes and unassisted codes. Furthermore, we derive two SDP strong converse bounds for the classical capacity of general quantum channels: for any code with a rate exceeding either of the two bounds of the channel, the success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bounds, we derive an improved upper bound on the classical capacity of the amplitude damping channel. We also establish the strong converse property for the classical and private capacities of a new class of quantum channels. We finally study the zero-error setting and provide efficiently computable upper bounds on the one-shot zero-error capacity of a general quantum channel.

arXiv:1610.06381•IEEE Transactions on Information Theory•Aug 17, 2017•69 citations

The n-shot classical capacity of the quantum erasure channel

Matteo Rosati

Abstract We compute the n-shot classical capacity of the quantum erasure channel, providing upper bounds and almost-matching lower bounds for it, the latter achievable via large-minimum-distance classical linear codes for any n. The protocols are in full product form, i.e. no entanglement is needed either at the encoder or decoder to attain the capacity, and they explicitly adapt to the transition between different error regimes as the erasure probability increases. Finally, we show that our upper and lower bounds on the capacity are tighter than those obtainable from the general theory of finite-size capacity via generalized divergences.

Journal of Physics Communications•Aug 1, 2024•2 citations
The aim of this work is to study the zero-error capacity of pure-state classical-quantum channels in the setting of list decoding. We provide an achievability bound for list-size two and a converse bound holding for every fixed list size. The two bounds coincide for channels whose pairwise absolute state overlaps form a positive semi-definite matrix. Finally, we discuss a remarkable peculiarity of the classical-quantum case: differently from the fully classical setting, the rate at which the sphere-packing bound diverges might not be achievable by zero-error list codes, even when we take the limit of fixed but arbitrarily large list size.
In this paper, the sphere packing bound of Fano, Shannon, Gal- lager and Berlekamp and the zero-rate bound of Berlekamp are extended to general classical-quantum channels. The upper bound for the reliability func- tion obtained from the sphere packing coincides at high rates, for the case of pure state channels, with a lower bound derived by Burnashev and Holevo (21). Thus, for pure state channels, the reliability function at high rates is now ex- actly determined. For the general case, the obtained upper bound expression at high rates was conjectured to represent also a lower bound to the reliability function, but a complete proof has not been obtained yet. Finally, the obtained zero-rate upper bound to the reliability function of a general classical-quantum channel with no zero-error capacity coincides with a lower bound obtained by Holevo, thus determining the exact expression.
In this paper, lower bounds on error probability in coding for discrete classical and classical-quantum channels are studied. The contribution of the paper goes in two main directions: 1) extending classical bounds of Shannon to classical-quantum channels, and 2) proposing a new framework for lower bounding the probability of error of channels with a zero-error capacity in the low rate region. The relation between these two problems is revealed by showing that Lovász' bound on zero-error capacity emerges as a natural consequence of the sphere packing bound once we move to the more general context of classical-quantum channels. A variation of Lovász' bound is then derived to lower bound the probability of error in the low rate region by means of auxiliary channels. As a result of this study, connections between the Lovász theta function, the expurgated bound of Gallager, the cutoff rate of a classical channel, and the sphere packing bound for classical-quantum channels are established.
We study lower bounds on the optimal error probability in classical coding over classical-quantum channels at rates below the capacity, commonly termed quantum sphere-packing bounds. Winter and Dalai have derived such bounds for classical-quantum channels; however, the exponents in their bounds only coincide when the channel is classical. In this paper, we show that these two exponents admit a variational representation and are related by the Golden-Thompson inequality, reaffirming that Dalai's expression is stronger in general classical-quantum channels. Second, we establish a finite blocklength sphere-packing bound for classical-quantum channels, which significantly improves Dalai's prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(logn/n), indicating our sphere-packing bound is almost exact in the high rate regime. Finally, for a special class of symmetric classical-quantum channels, we can completely characterize its optimal error probability without the constant composition code assumption. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
We study lower bounds on the optimal error probability in channel coding at rates below capacity, commonly termed sphere-packing bounds. In this work, we establish a sphere-packing bound for classical-quantum channels, which significantly improves previous prefactor from the order of subexponential to polynomial. Furthermore, the gap between the obtained error exponent for constant composition codes and the best known classical random coding exponent vanishes in the order of o(log n/n), indicating our sphere-packing bound is almost exact in the high rate regime. The main technical contributions are two converse Hoeffding bounds for quantum hypothesis testing and the saddle-point properties of error exponent functions.
We investigate the classical communication over quantum channels when assisted by no-signaling and positive-partial-transpose-preserving (PPT) codes, for which both the optimal success probability of a given transmission rate and the one-shot E-error capacity are formalized as semidefinite programs (SDPs). Based on this, we obtain improved SDP finite blocklength converse bounds of general quantum channels for entanglement-assisted codes and unassisted codes. Furthermore, we derive two SDP strong converse bounds for the classical capacity of general quantum channels: for any code with a rate exceeding either of the two bounds of the channel, the success probability vanishes exponentially fast as the number of channel uses increases. In particular, applying our efficiently computable bounds, we derive an improved upper bound on the classical capacity of the amplitude damping channel. We also establish the strong converse property for the classical and private capacities of a new class of quantum channels. We finally study the zero-error setting and provide efficiently computable upper bounds on the one-shot zero-error capacity of a general quantum channel.
Abstract We compute the n-shot classical capacity of the quantum erasure channel, providing upper bounds and almost-matching lower bounds for it, the latter achievable via large-minimum-distance classical linear codes for any n. The protocols are in full product form, i.e. no entanglement is needed either at the encoder or decoder to attain the capacity, and they explicitly adapt to the transition between different error regimes as the erasure probability increases. Finally, we show that our upper and lower bounds on the capacity are tighter than those obtainable from the general theory of finite-size capacity via generalized divergences.