Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels

Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter · 2025

Read Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels by Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20991.txt.

Introduction

Pau Colomer and co-authors prove a quantum version of a coding lemma in a 2025 paper. The setting is deterministic identification, a task where a receiver only needs to tell whether a specific message was sent, not decode every message. Their earlier work set conditions for good codes of this kind over classical channels.

Here they give the full quantum analogue: a good code exists when the channel's output states can be packed in a suitable way in a modified state space. The code is built from product states drawn from that packing. The result sharpens the known lower bound on capacity beyond an older decoding approach and ties the bound to the fractal size of a state space. A worked channel example shows an optimal code.

Catalog record

CREATORPau Colomer, Christian Deppe, Holger Boche, Andreas Winter
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20991

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter Abstract In our previous work, we presented the Hypothesis Testing Lemma , a key tool that establishes sufficient conditions for the existence of good deterministic identification (DI) codes for memoryless channels with finite output, but arbitrary input alphabets. In this work, we provide a full quantum analogue of this lemma, which shows that the existence of a DI code in the quantum setting follows from a suitable packing in a modified space of output quantum states. Specifically, we demonstrate that such a code can be constructed using product states derived from this packing. This result enables us to tighten the capacity lower bound for DI over quantum channels beyond the simultaneous decoding approach. In particular, we can now express these bounds solely in terms of the Minkowski dimension of a certain state space, giving us new insights to better understand the nature of the protocol, and the separation between simultaneous and non-simultaneous codes. We extend the discussion with a particular channel example for which we can construct an optimum code. I Introduction Shannon’s classical model of communication [ 1 ] can be generalized to a quantum setting where a receiver aims to reconstruct a classical message encoded in a quantum state and sent through n uses of a memoryless quantum channel. In such a setting, the number of distinct messages M that can be reliably transmitted – that is, with arbitrarily small probability of error for sufficiently long codewords – grows exponentially with n , leading to the linear relation \log M\sim Rn , with R=\frac{1}{n}\log M the \emph{rate} of the code, and \log the binary logarithm. The supremum of all achievable rates in the asymptotic limit of large n is known as the capacity C and is given by the celebrated Holevo-Schumacher-Westmoreland (HSW) theorem and some subsequent refinements [ 2 , 3 , 4 , 5 ] . This setting contrasts with the identification problem, where the receiver is not required to recover the sent message, but only to check whether it matches a specific message of his interest. The decoding is therefore limited to a hypothesis test, reducing the communication complexity of the task [ 6 ] . A full characterization of identification over classical discrete memoryless channels (DMCs) was first provided by Ahlswede and Dueck [ 7 ] , and later generalized to the quantum setting by Löber [ 8 ] . Their results show that the number N of identifiable messages can grow exponentially faster with the number n of uses of the channel than in transmission, i.e., \log N\sim 2^{nR} . This means that we can identify exponentially more messages than we can transmit. Interestingly, the exponential increase of the code size that identification codes offer is lost if deterministic encodings (without any use of randomness) are imposed. As a matter of fact, it was already noted in [ 7 ] that DI over any DMC could only achieve a linear scaling with n (the same as in transmission). Deterministic codes, however, are in general easier to implement, simulate, and to explicitly construct [ 9 , 10 , 11 ] ; so, in spite of the poorer performance, an interest was kept in DI codes due to potential applications. This interest was renewed when it was proven that certain channels with continuous input can have superlinear scaling \log N\sim Rn\log n of the code size [ 12 , 13 ] . That is, better than transmission and DI over DMCs, which can only achieve a linear scaling; but worse than general randomized identification, which can achieve an exponential scaling in the code size logarithm \log N . In recent work [ 14 , 15 , 16 , 17 ] , it has been proven that this superlinear behaviour exhibited in DI codes over some channels is in fact a general feature of deterministic identification over channels W with discrete output \mathcal{Y} but arbitrary input alphabets \mathcal{X} , and that the corresponding capacities are related to the fractal dimension of a certain modification of the output probability set. The code construction part of these results is based on the so-called Hypothesis Testing Lemma, which shows that the entropy typical set \mathcal{T}_{x^{n}}^{\delta} for each possible code word x^{n} , and 0<\delta\leq\sqrt{n}\log|\mathcal{Y}| can be a decent surrogate of the optimal identification test: Lemma I.1 (Colomer et al. [ 15 ] ) . Consider n uses of the classical channel W:\mathcal{X}\rightarrow\mathcal{Y} and two points x^{n},{x^{\prime}}^{n}\in\mathcal{X}^{n} such that 1-\frac{1}{2}\left\|W_{x^{n}}-W_{{x^{\prime}}^{n}}\right\|_{1}\leq\epsilon . Then, \begin{split}W_{{x^{\prime}}^{n}}(\mathcal{T}_{x^{n}}^{\delta})&\leq 2\exp\left(-\delta^{2}/36K(|\mathcal{Y}|)\right)\\ &\quad+\epsilon\left(1+2^{2\delta\sqrt{n}}2^{H(W_{x^{n}})-H(W_{{x^{\prime}}^{n}})}\right),\end{split} with K(d)=(\log\max\{d,3\})^{2} , W_{x^{n}} the output probability distribution of the input x^{n} , and H(W_{x^{n}}) the corresponding Shannon entropy. ∎ From this, it is shown that a good classical DI code can be constructed just from a packing in the output probability space with large enough distance between its elements [ 15 , Thm. III.2] . The performance of such code can be then studied to calculate an achievability (lower) bound for the classical DI capacity [ 15 , Thm. V.7] . These results are not directly generalizable to the quantum setting as Lemma I.1 is not available for quantum states. However, through a couple of tricks, the classical lemma can be generalised to the quantum case. Let us prepare the ground with some definitions. Definition I.2 . An (n,N,\lambda_{1},\lambda_{2}) - DI code for a classical-quantum channel W:\mathcal{X}\rightarrow\mathcal{S}(B) is a collection \{(u_{j},E_{j}):j\in[N]\} of code words u_{j}\in\mathcal{X}^{n} and POVM elements 0\leq E_{j}\leq\mathds{1} on B^{n} , such that for all j\neq k\in[N] \Tr W_{u_{j}}^{n}E_{j}\geq 1-\lambda_{1},\quad\Tr W^{n}_{u_{j}}E_{k}\leq\lambda_{2}, where W^{n}_{u_{j}}=W_{x_{1}}\otimes\cdots\otimes W_{x_{n}}\in\mathcal{S}(B^{n}) is the output quantum state when the input sequence is u_{j}=x_{1}\ldots x_{n}\in\mathcal{X}^{n} . The largest N such that an (n,N,\lambda_{1},\lambda_{2}) -DI code exists is denoted N_{\text{DI}}(n,\lambda_{1},\lambda_{2}) . Notice that, while in quantum transmission the decoding consists of a fixed POVM, the outcome of which is used to guess the message that was sent; in identification, the measurement the receiver applies is dependent on the message j\in[N] that he wants to identify, for which the hypothesis test (E_{j},\mathds{1}-E_{j}) is going to serve as decoder. The different effects E_{j} do not necessarily need to be the elements of a POVM. In fact, due to the possibility of complementarity of quantum observables, in general the tests (E_{j},\mathds{1}-E_{j}) are not even simultaneously measurable. However, if we insist that they are, meaning that there is a POVM (D_{m}:m\in\mathcal{M}) on B^{n} such that each (E_{j},\mathds{1}-E_{j}) is a coarse-graining of it, i.e. there is a subset \mathcal{M}_{j}\subset\mathcal{M} with E_{j}=\sum_{m\in\mathcal{M}_{j}}D_{m} , the DI code is called simultaneous [ 8 ] . The largest code size is then denoted N_{\text{DI}}^{\text{sim}}(n,\lambda_{1},\lambda_{2}) . The main finding of [ 15 ] is that the message length \log N of DI codes generically scales as n\log n , thus motivating the definition of the slightly superlinear DI capacity as \dot{C}_{\text{DI}}(W):=\inf_{\lambda_{1},\lambda_{2}>0}\liminf_{n\rightarrow\infty}\frac{1}{n\log n}\log N_{\text{DI}}(n,\lambda_{1},\lambda_{2}), and similarly for the simultaneous DI capacity \dot{C}_{\text{DI}}^{\text{sim}}(W) . There is a simple way of constructing a simultaneous DI code for the cq-channel W : choose a POVM T=(T_{y}:y\in\mathcal{Y}) on B and concatenate W with it, obtaining a classical channel \overline{W}(y|x)=\Tr W_{x}T_{y} . Using the same measurement T on each of the n channel uses transforms the cq-channel W^{n} into the classical

Read the complete text