Identification of ­messages via channels ­follows curious rules

The original proposal was a three-pronged research program dedicated to advancing quantum and classical Shannon theory: (1) security notions and associated capacities for wiretap channels, (2) identification via quantum channels, (3) entropy inequalities. While I have conducted research in all three lines – on (3) with Joseph Schindler et al [1]., and on (1) with other collaborators [2] [3] [4] – with the TUM-IAS Focus Group we almost immediately embarked on a deeper investigation of deterministic identification (DI) via memoryless noisy channels, motivated by earlier work of Holger Boche, Christian Deppe, and collaborators on discrete, Gaussian, and Poisson channels. These had revealed a curious independence of the capacity of the noise in the channel, and the latter two a linearithmic growth of the message length (i.e., Rn log n). Within the Focus Group, and in particular with doctoral candidate Pau Colomer, we decided to look at deterministic identification in general channels, both classical and quantum, to obtain a broad theoretical understanding of this task. While the communication diagram of identification is similar to Shannon’s transmission diagram, note that in the former, in contrast to the latter, the receiver is not trying to decode the unknown message m, but only to answer a simple yes-no question: Is the sent message equal to m’, where m’ is known at the receiver but not the sender (Fig. 1). Before us, no one had looked at DI in generality, nor had there been any results on quantum channels. The main findings of this research, published in conference and journal papers as well as preprints, are as follows:

(a) For channels with discrete output, we find that the linearithmic message length is generic, and the constant R in front is, up to an unknown prefactor between ¼ and ½, equal to the Minkowski fractal dimension of a point set associated to the output distributions of the channel (Fig. 2) [5]. This is a most curious result, as usually capacities are related to metric aspects of the channel output states, whereas here the scale-invariant dimension emerges. In the same paper, we show that dimension zero is possible and leads to characteristic message lengths between n and n log n. Furthermore, we show that the DI capacity can exhibit superactivation: i.e., the combination of two zero-capacity channels has positive capacity.

(b) Still in Ref. 5, we transport the main points of this theory to classical-quantum channels and quantum channels with product state encodings. A subtlety arising here is that the DI code could be simultaneous or non-simultaneous, referring to whether the receiver’s tests for the different messages m’ are coexistent or not. The Minkowski dimension appearing is either that of a classical shadow of the channel or of a point set of density matrices. Later [6], we found matching capacity upper and lower bounds on the non-simultaneous DI capacity, while the matching converse bound for the simultaneous coding theorem from Ref. 5 remains an open problem.

(c) Noting that in these results the two error probabilities vanish but converge slowly, we decided to investigate what happens when one or both of them converge to zero exponentially. This was motivated by rate-reliability theory for transmission: It had long been known that at rates below the capacity the error probability is exponentially small. Indeed, in that case for fixed error exponent E we get back “only” linear growth, the code length being asymptotically R(-log E)n, where R is again the Minkowski dimension, up to the same unknown prefactor between ¼ and ½ as before [7].

(d) We have explored DI in quantum channels in another direction, too, considering that the crucial feature for classical channels is the absence of randomization, and hence perhaps pure state inputs offer a quantum analog. We show, however [8], that identification via quantum channels with pure state inputs is more akin to fully randomized identification, with its characteristic exponential growth of the message length (2^nR). In particular, we  show that the (exponential-scale) simultaneous identification capacity of a quantum channel is attained with pure state encodings. This implied the resolution of a long-standing conjecture about the separation between simultaneous and non-simultaneous identification capacities [9]

These outcomes, and many of the others from the complete reference list of the project, are already informing current and future research in quantum Shannon theory. Future directions in the DI problem we are planning to attack are determination of the mysterious universal prefactor between ¼ and ½, clarification of the role of simultaneous decoding in DI, and extensions to quantum state identification and K-identification. Personally, I hope we can return to one of my original motivations for looking at DI, namely bit string commitment via noisy channels [11], whose capacity formulas are clarified by deterministic identification featuring as a sub-protocol. These questions will continue to link me to my hosts and their groups at TUM, but also reinforce my close collaboration with Dr. Christian Deppe (who left TUM halfway through the project and is now at Technische Universität Braunschweig).

This report wouldn’t be complete without a mention of the organisation, at the TUM-IAS, of the immensely successful workshop “Beyond IID in Information Theory,” July 14–18, 2025, which brought together more than 100 researchers from the international community:

See also: https://sites.google.com/view/beyondiid13 for the scientific program and details.

Selected publications

[5] P. Colomer and A. Winter, “Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks,” Communications in Mathematical Physics, vol. 405, no. 11, art. 281, Nov 2024. doi: 10.1007/s00220-024-05156-7. arXiv:2304.12114 [quant-ph].
 

[6] P. Colomer, C. Deppe, H. Boche, and A. Winter, “Zero-entropy encoders and simultaneous decoders in identification via quantum channels,” in: Information Theory and Related Fields: Essays in Memory of Ning Cai, LNCS, vol. 14620, Berlin: Springer Verlag, 2025b, pp. 478–502. doi: 10.1007/978-3-031-82014-4_18. arXiv:2402.09116 [quant-ph].
 

[7] P. Colomer, C. Deppe, H. Boche, and A. Winter, “Deterministic identification over channels with finite output: A dimensional perspective on superlinear rates,” IEEE Transactions on Information Theory, vol. 71, no. 5, pp. 3373–3396, Jan. 2025a. doi: 10.1109/TIT.2025.3531301. arXiv:2402.09117 [cs.IT].
 

[8] P. Colomer, C. Deppe, H. Boche, and A. Winter, “Rate-Reliability tradeoff for deterministic Identification,” IEEE Transactions on Communications, vol. 73, no. 12, pp. 14107-14123, Aug. 2025c. doi: 10.1109/TCOMM.2025.3594790. arXiv:2502.02389 [cs.IT].
 

[10] P. Colomer, H. Boche, and A. Winter, “Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels,” in: Proc. 2025 IEEE International Symposium on Information Theory (ISIT), pp. 1–5, Ann Arbor, Michigan, Jun. 2025. doi: 10.1109/ISIT63088.2025. 11195315. arXiv:2504.20991 [cs.IT].

Full list of publications