Post-Shannon Quantum Communication and (Unexpected) Links between Computing and Information Processing

Abstract

The talk first introduces performance requirements and post Shannon communication tasks for future quantum communication networks. Following this, the post Shannon communication tasks "identification of messages" and "secure identification of messages" will be discussed in detail and corresponding capacities will be derived. It turns out that these communication tasks behave quite unexpectedly compared to "Shannon's message transmission" communication tasks. This also applies to "identification of messages" with feedback and entanglement assistance. Subsequently, it will be shown that important capacities are not Turing computable, i.e. they can never be calculated or simulated on digital hardware with performance guarantees. Continuing with these results, the second part of the talk will examine methods of information processing and physical theories regarding their computability on Turing machines. Some questions of computability and connections to Research Unit B, quantum simulation, and to Research Unit C, quantum computing, will be discussed. A large number of information processing tasks and physical theories will be identified that are not computable on Turing machines, i.e. ones that can never be simulated on a Turing machine with performance guarantees. For some of these problems, "implementations" on "ideal analog computers" are possible. Thus on the level of "abstract machine models" for computation it turns out that for these tasks the "ideal analog computer" is more powerful than the ideal digital computing model of "Turing Machine".