ONE-SHOT PROTOCOLS FOR COMMUNICATION OVER QUANTUM NETWORKS: ACHIEVABILITY AND LIMITATIONS

Abstract

This thesis studies the problems of source compression and channel coding in the one-shot entanglement-assisted quantum setting. The main contribution of the first part of the thesis is to systematically develop one-shot protocols for various quantum tasks, using two unified tools of `convex-split' and `position-based decoding'. Convex-split is used for the encoding operations and position-based decoding, which can also be viewed as a dual to the convex-split, is used for decoding operation. Our protocols and achievability results closely resemble the corresponding protocols and results in the classical case. Furthermore, position-based decoding gives near optimal one-shot results for the point to point channel.

In the second part of the thesis, we exhibit some limitations on how well quantum messages can be compressed. We show that efficient classical schemes, such as the Huffman coding scheme, are not possible in the quantum domain. As a complementary result, we show an exponential separation between quantum communication complexity and quantum information complexity. This shows the existence of a hard to compress interactive quantum protocol.