Continuing our earlier work (quant-ph/0401060), we give two alternative proofs of the result that a noiseless qubit channel has identification capacity 2: the first is direct by a "maximal code with random extension" argument, the second is by showing that 1 bit of entanglement (which can be generated by transmitting 1 qubit) and negligible (quantum) communication has identification capacity 2. This generalises a random hashing construction of Ahlswede and Dueck: that 1 shared random bit together with negligible communication has identification capacity 1. We then apply these results to prove capacity formulas for various quantum feedback channels: passive classical feedback for quantum-classical channels, a feedback model for classical-quantum channels, and "coherent feedback" for general channels.
Continuing our earlier work (quant-ph/0401060), we give two alternative proofs of the result that a noiseless qubit channel has identification capacity 2: the first is direct by a "maximal code with random extension" argument, the second is by showing that 1 bit of entanglement (which can be generated by transmitting 1 qubit) and negligible (quantum) communication has identification capacity 2. This generalises a random hashing construction of Ahlswede and Dueck: that 1 shared random bit together with negligible communication has identification capacity 1. We then apply these results to prove capacity formulas for various quantum feedback channels: passive classical feedback for quantum-classical channels, a feedback model for classical-quantum channels, and "coherent feedback" for general channels.
We discuss concepts of message identification in the sense of Ahlswede and Dueck via general quantum channels, extending investigations for classical channels, initial work for classical-quantum (cq) channels and "quantum fingerprinting". We show that the identification capacity of a discrete memoryless quantum channel for classical information can be larger than that for transmission; this is in contrast to all previously considered models, where it turns out to equal the common randomness capacity (equals transmission capacity in our case): in particular, for a noiseless qubit, we show the identification capacity to be 2, while transmission and common randomness capacity are 1. Then we turn to a natural concept of identification of quantum messages (i.e. a notion of "fingerprint" for quantum states). This is much closer to quantum information transmission than its classical counterpart (for one thing, the code length grows only exponentially, compared to double exponentially for classical identification). Indeed, we show how the problem exhibits a nice connection to visible quantum coding. Astonishingly, for the noiseless qubit channel this capacity turns out to be 2: in other words, one can compress two qubits into one and this is optimal. In general however, we conjecture quantum identification capacity to be different from classical identification capacity.
We discuss concepts of message identification in the sense of Ahlswede and Dueck via general quantum channels, extending investigations for classical channels, initial work for classical--quantum (cq) channels and ``quantum fingerprinting''. We show that the identification capacity of a discrete memoryless quantum channel for classical information can be larger than that for transmission; this is in contrast to all previously considered models, where it turns out to equal the common randomness capacity (equals transmission capacity in our case): in particular, for a noiseless qubit, we show the identification capacity to be 2, while transmission and common randomness capacity are 1. Then we turn to a natural concept of identification of quantum messages (i.e. a notion of ``fingerprint'' for quantum states). This is much closer to quantum information transmission than its classical counterpart (for one thing, the code length grows only exponentially, compared to double exponentially for classical identification). Indeed, we show how the problem exhibits a nice connection to visible quantum coding. Astonishingly, for the noiseless qubit channel this capacity turns out to be 2: in other words, one can compress two qubits into one and this is optimal. In general however, we conjecture quantum identification capacity to be different from classical identification capacity.
We analyze message identification via Gaussian channels with noiseless feedback, which is part of the Post Shannon theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. If the noise variance is positive, we propose a coding scheme that generates infinite common randomness between the sender and the receiver. We show that any identification rate via the Gaussian channel with noiseless feedback can be achieved. The remarkable result is that this applies to both rate definitionsn1logM(as defined by Shannon for transmission) andn1loglogM— (as defined by Ahlswede and Dueck for identification). We can even show that our result holds regardless of the selected scaling for the rate. A detailed version with all proofs, explanations and more discussions can be found in [1].
We analyze message identification via Gaussian channels with noiseless feedback, which is part of the Post Shannon theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. If the noise variance is positive, we propose a coding scheme that generates infinite common randomness between the sender and the receiver. We show that any identification rate via the Gaussian channel with noiseless feedback can be achieved. The remarkable result is that this applies to both rate definitions n1logM (as defined by Shannon for transmission) and n1loglogM — (as defined by Ahlswede and Dueck for identification). We can even show that our result holds regardless of the selected scaling for the rate. A detailed version with all proofs, explanations and more discussions can be found in [1].
We initiate the study of zero-error communication via quantum channels when the receiver and the sender have at their disposal a noiseless feedback channel of unlimited quantum capacity, generalizing Shannon's zero-error communication theory with instantaneous feedback. We first show that this capacity is only a function of the linear span of Choi-Kraus operators of the channel, which generalizes the bipartite equivocation graph of a classical channel, and which we dub non-commutative bipartite graph. Then, we go on to show that the feedback-assisted capacity is non-zero (allowing for a constant amount of activating noiseless communication) if and only if the non-commutative bipartite graph is non-trivial, and give a number of equivalent characterizations. This result involves a far-reaching extension of the conclusive exclusion of quantum states. We then present an upper bound on the feedback-assisted zero-error capacity, motivated by a conjecture originally made by Shannon and proved later by Ahlswede. We demonstrate that this bound to have many good properties, including being additive and given by a minimax formula. We also prove a coding theorem showing that this quantity is the entanglement-assisted capacity against an adversarially chosen channel from the set of all channels with the same Choi-Kraus span, which can also be interpreted as the feedback-assisted unambiguous capacity. The proof relies on a generalization of the Postselection Lemma (de Finetti reduction) that allows to reflect additional constraints, and which we believe to be of independent interest. This capacity is a relaxation of the feedback-assisted zero-error capacity; however, we have to leave open the question of whether they coincide in general. We illustrate our ideas with a number of examples, including classical-quantum channels and Weyl diagonal channels, and close with an extensive discussion of open questions.
Classical identification via a noisy channel is a communication task in which the receiver is not required to reconstruct the full transmitted message, but only to decide whether it coincides with a message of interest. This relaxation allows the number of identifiable messages to grow doubly exponentially with the blocklength. For quantum channels, the resulting (doubly exponential) identification capacity CID can strictly exceed the ordinary (exponential) transmission capacity C.
In this paper, we prove that the entanglement-assisted transmission capacity CE is a strong converse bound for this task: CID≤CE. For sufficiently low-noise channels, this bound can also be achieved via the Hayden-Winter (quantum) identification + fingerprinting codes. This yields an exact characterization CID=CE of identification capacity for such channels. However, for general channels, we prove that this upper bound can be strict. We exhibit an explicit family of transpose-depolarizing channels for which CID<CE. As a consequence, we also obtain the first example of strict superadditivity of the identification capacity CID.