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:1509.00715 · IEEE Transactions on Information Theory

Constant Compositions in the Sphere Packing Bound for Classical-Quantum Channels

Marco Dalai, Andreas Winter

Published Jan 1, 2017• 28 citations
arXivHTMLPDF

Abstract

The sphere packing bound, in the form given by Shannon, Gallager, and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant-composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is finally applied to auxiliary channels to deduce a bound, which is useful in the low rate region and which can be interpreted as an extension of the Elias bound.

DOI
10.1109/tit.2017.2726555

Related papers

Constant compositions in the sphere packing bound for classical-quantum channels

Marco Dalai, Andreas Winter

The sphere packing bound, in the form given by Shannon, Gallager and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is then applied to auxiliary channels to deduce a bound which can be interpreted as an extension of the Elias bound.

arXiv:1401.6039•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•13 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

Sphere packing bound for quantum channels

Marco Dalai

In this paper, the Sphere-Packing-Bound of Fano, Shannon, Gallager and Berlekamp is extended to general classical-quantum channels. The obtained upper bound for the reliability function, for the case of pure-state channels, coincides at high rates with a lower bound derived by Burnashev and Holevo [1]. Thus, for pure state channels, the reliability function at high rates is now exactly 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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•10 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

Lovász's theta function, Rényi's divergence and the sphere-packing bound

Marco Dalai

Lovász's bound to the capacity of a graph and the the sphere-packing bound to the probability of error in channel coding are given a unified presentation as information radii of the Csiszár type using the Rényi divergence in the classical-quantum setting. This brings together two results in coding theory that are usually considered as being of a very different nature, one being a “combinatorial” result and the other being “probabilistic”. In the context of quantum information theory, this difference disappears.

arXiv:1301.6339•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•7 citations

Zero-Error List Decoding for Classical-Quantum Channels

Marco Dalai, Filippo Girardi, Ludovico Lami

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.

quant-pharXiv:2601.09786•IEEE International Symposium on Information Theory (ISIT)•Jan 16, 2026•2 citations
The sphere packing bound, in the form given by Shannon, Gallager, and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant-composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is finally applied to auxiliary channels to deduce a bound, which is useful in the low rate region and which can be interpreted as an extension of the Elias bound.
The sphere packing bound, in the form given by Shannon, Gallager and Berlekamp, was recently extended to classical-quantum channels, and it was shown that this creates a natural setting for combining probabilistic approaches with some combinatorial ones such as the Lovász theta function. In this paper, we extend the study to the case of constant composition codes. We first extend the sphere packing bound for classical-quantum channels to this case, and we then show that the obtained result is related to a variation of the Lovász theta function studied by Marton. We then propose a further extension to the case of varying channels and codewords with a constant conditional composition given a particular sequence. This extension is then applied to auxiliary channels to deduce a bound which can be interpreted as an extension of the Elias bound.
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.
In this paper, the Sphere-Packing-Bound of Fano, Shannon, Gallager and Berlekamp is extended to general classical-quantum channels. The obtained upper bound for the reliability function, for the case of pure-state channels, coincides at high rates with a lower bound derived by Burnashev and Holevo [1]. Thus, for pure state channels, the reliability function at high rates is now exactly 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.
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.
Lovász's bound to the capacity of a graph and the the sphere-packing bound to the probability of error in channel coding are given a unified presentation as information radii of the Csiszár type using the Rényi divergence in the classical-quantum setting. This brings together two results in coding theory that are usually considered as being of a very different nature, one being a “combinatorial” result and the other being “probabilistic”. In the context of quantum information theory, this difference disappears.
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.