We study commitment scheme for classical-quantum channels. To accomplish this we define various notions of commitment capacity for these channels and prove matching upper and lower bound on it in terms of the conditional entropy. Our achievability (lower bound) proof is quantum generalisation of the work of one of the authors (arXiv:2103.11548) which studied the problem of secure list decoding and its application to bit-string commitment. The techniques we use in the proof of converse (upper bound) is similar in spirit to the techniques introduced by Winter, Nascimento and Imai (Cryptography and Coding 2003) to prove upper bound on the commitment capacity of classical channels. However, generalisation of this technique to the quantum case is not so straightforward and requires some new constructions, which can be of independent interest.We study commitment scheme for classical-quantum channels. To accomplish this we define various notions of commitment capacity for these channels and prove matching upper and lower bound on it in terms of the conditional entropy. Our achievability (lower bound) proof is quantum generalisation of the work of one of the authors (arXiv:2103.11548) which studied the problem of secure list decoding and its application to bit-string commitment. The techniques we use in the proof of converse (upper bound) is similar in spirit to the techniques introduced by Winter, Nascimento and Imai (Cryptography and Coding 2003) to prove upper bound on the commitment capacity of classical channels. However, generalisation of this technique to the quantum case is not so straightforward and requires some new constructions, which can be of independent interest.

IEEE International Symposium on Information Theory (ISIT)Jun 26, 20225 citations

Commitment capacity of classical-quantum channels

Masahito Hayashi, Naqueeb Ahmad Warsi

arXiv:2201.06333Jan 17, 20220 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.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.09786IEEE International Symposium on Information Theory (ISIT)Jan 16, 20260 citations

Secure List Decoding and its Application to Bit-String Commitment

Masahito Hayashi

We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver’s uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way.We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver’s uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way.

arXiv:2103.11548IEEE Transactions on Information TheoryFeb 9, 20225 citations

Tight Lower Bound on the Error Exponent of Classical-Quantum Channels

Joseph M. Renes

A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constant $E(W,R)$ which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constant$E(W,R)$which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.

arXiv:2407.11118IEEE Transactions on Information TheoryNov 20, 20247 citations

Reliability Function of Classical-Quantum Channels

Ke Li, Dong Yang

We study the reliability function of general classical-quantum channels, which describes the optimal exponent of the decay of decoding error when the communication rate is below the capacity. As the main result, we prove a lower bound, in terms of the quantum Rényi information in Petz's form, for the reliability function. This resolves Holevo's conjecture proposed in 2000, a long-standing open problem in quantum information theory. It turns out that the obtained lower bound matches the upper bound derived by Dalai in 2013, when the communication rate is above a critical value. Thus, we have determined the reliability function in this high-rate case. Our approach relies on Renes' breakthrough made in 2022, which relates classical-quantum channel coding to that of privacy amplification, as well as our new characterization of the channel Rényi information.We study the reliability function of general classical-quantum channels, which describes the optimal exponent of the decay of decoding error when the communication rate is below the capacity. As the main result, we prove a lower bound, in terms of the quantum Rényi information in Petz's form, for the reliability function. This resolves Holevo's conjecture proposed in 2000, a long-standing open problem in quantum information theory. It turns out that the obtained lower bound matches the upper bound derived by Dalai in 2013, when the communication rate is above a critical value. Thus, we have determined the reliability function in this high-rate case. Our approach relies on Renes' breakthrough made in 2022, which relates classical-quantum channel coding to that of privacy amplification, as well as our new characterization of the channel Rényi information.

arXiv:2407.12403Physical Review LettersJan 8, 202511 citations

A fundamental quantity of interest in Shannon theory, classical or quantum, is the error exponent of a given channel W and rate R: the constant

E(W,R)

which governs the exponential decay of decoding error when using ever larger optimal codes of fixed rate R to communicate over ever more (memoryless) instances of a given channel W. Nearly matching lower and upper bounds are well-known for classical channels. Here I show a lower bound on the error exponent of communication over arbitrary classical-quantum (CQ) channels which matches Dalai’s sphere-packing upper bound for rates above a critical value, exactly analogous to the case of classical channels. This proves a conjecture made by Holevo in his investigation of the problem. Unlike the classical case, however, the argument does not proceed via a refined analysis of a suitable decoder, but instead by leveraging a bound by Hayashi on the error exponent of the cryptographic task of privacy amplification. This bound is then related to the coding problem via tight entropic uncertainty relations and Gallager’s method of constructing capacity-achieving parity-check codes for arbitrary channels. Along the way, I find a lower bound on the error exponent of the task of compression of classical information relative to quantum side information that matches the sphere-packing upper bound of Cheng et al. In turn, the polynomial prefactors to the sphere-packing bound found by Cheng et al. may be translated to the privacy amplification problem, sharpening a recent result by Li, Yao, and Hayashi, at least for linear randomness extractors.