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

Allerton Conference on Communication, Control, and Computing

Refinement of the sphere packing bound for symmetric channels

Yücel Altuğ, Aaron B. Wagner

Published Sep 1, 2011• 17 citations
Publisher

Abstract

We provide an improved sphere packing bound for positive and symmetric discrete memoryless channels that significantly improves the pre-factor in front of the exponent. Specifically, the presented bound decays only polynomially in N. Further, for the binary symmetric channel, the order of our pre-factor is tight.
DOI
10.1109/allerton.2011.6120146

Related papers

Refinement of the sphere-packing bound

Yücel Altuğ, Aaron B. Wagner

We provide a refinement of the sphere-packing bound for constant composition codes over discrete memoryless channels that improves the pre-factor in front of the exponential term. The order of our pre-factor is O(N-1/2(1+ρ*R)), where ρ*Ris related to the slope of the sphere-packing exponent and N is the blocklength.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•8 citations

Sphere-packing bound for symmetric classical-quantum channels

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

“To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award.” We provide a sphere-packing lower bound for the optimal error probability in finite blocklengths when coding over a symmetric classical-quantum channel. Our result shows that the pre-factor can be significantly improved from the order of the subexponential to the polynomial, This established pre-factor is arguably optimal because it matches the best known random coding upper bound in the classical case. Our approaches rely on a sharp concentration inequality in strong large deviation theory and crucial properties of the error-exponent function.

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

A Simple Derivation of The Refined Sphere-Packing Bound for Classical-Quantum Channels

Bo-An Shi, Hao–Chung Cheng

The refined sphere-packing bound refers to a tight exponential lower bound to the error probability in channel coding. In the work, we present a derivation of the non-asymptotic refined sphere-packing bound for classical-quantum channels with constant composition codes. Our derivation not only offers much simpler and more transparent arguments, but also deepens the conceptual understanding of the relations between the tilted distribution and hypothesis testing.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•1 citation

Extension of the Poltyrev Bound to Binary Memoryless Symmetric Channels

Tal Philosof, Ariel Doubchak, Amit Berman +1 more

The Poltyrev bound provides a very tight upper bound on the decoding error probability when using binary linear codes for transmission over the binary symmetric channel and the additive white Gaussian noise channel, making use of the code's weight spectrum. In the present work, the bound is extended to symmetric binary-input memoryless channels with a discrete output alphabet. The derived bound is demonstrated on a hybrid BSC-BEC channel. Additionally, a reduced-complexity bound is introduced at the cost of some loss in tightness.

arXiv:2501.13021•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•1 citation

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
“To be considered for the 2017 IEEE Jack Keil Wolf ISIT Student Paper Award.” We provide a sphere-packing lower bound for the optimal error probability in finite blocklengths when coding over a symmetric classical-quantum channel. Our result shows that the pre-factor can be significantly improved from the order of the subexponential to the polynomial, This established pre-factor is arguably optimal because it matches the best known random coding upper bound in the classical case. Our approaches rely on a sharp concentration inequality in strong large deviation theory and crucial properties of the error-exponent function.
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.
The Poltyrev bound provides a very tight upper bound on the decoding error probability when using binary linear codes for transmission over the binary symmetric channel and the additive white Gaussian noise channel, making use of the code's weight spectrum. In the present work, the bound is extended to symmetric binary-input memoryless channels with a discrete output alphabet. The derived bound is demonstrated on a hybrid BSC-BEC channel. Additionally, a reduced-complexity bound is introduced at the cost of some loss in tightness.
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.