Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates

Following initial work by JaJa, Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by its output distributions as a subset in the probability simplex. Our main findings are that the maximum length of messages thus identifiable scales superlinearly as Rn log n with the block length n, and that the optimal rate R is bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension d of a certain algebraic transformation of the output set: 1/4 d ≤ R ≤ 1/2 d. Remarkably, both the lower and upper Minkowski dimensions play a role in this result. Along the way, we present a Hypothesis Testing Lemma showing that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits superactivation: there exist channels whose capacities individually are zero, but whose product has positive capacity. We also generalise these results to classical-quantum channels with finite-dimensional output quantum system, in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.