Tight lower bound on the error exponent of classical-quantum channels

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 IEEE TIT 59, 8027 (2013) 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 IEEE TIT 46, 2256 (2000). 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 CMP 333, 335 (2015). 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. IEEE TIT 67, 902 (2021). 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 IEEE TIT 69, 1680 (2023), at least for linear randomness extractors.