  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.
