2016/05/31 by Anurag Anshu, Ankit Garg, Aram W. Harrow +2
Computer Science · Engineering · Physics and Astronomy · #Independent and identically distributed random variables #Information theory #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum capacity #Quantum channel #Quantum entanglement #Quantum information #Quantum information science #Quantum mutual information #Upper and lower bounds #Von Neumann entropy #Wireless Communication Security Techniques #quant-ph
paper · pdf · doi:10.1109/tit.2018.2849066
published as IEEE Transactions on Information Theory (Volume: 64 , Issue: 11, Nov. 2018) · version 3, 54 pages, 4 figures. Added a near optimal bound (up to additive factors) for the expected communication cost of the main task. Section 5 contains the result from arXiv:1506.06380 . Conference version at http://drops.dagstuhl.de/opus/volltexte/2016/6684/
arxiv created 2017/12/28 · openalex created_date 2018/01/05 · openalex publication_date 2018/06/19 · arxiv updated 2018/10/23 · openalex updated_date 2026/08/06
A central question in the classical information theory is that of source compression, which is the task where Alice receives a sample from a known probability distribution and needs to transmit it to the receiver Bob with small error. This problem has a one-shot solution due to Huffman, in which the messages are of variable length and the expected length of the messages matches the asymptotic and independent identically distributed (i.i.d.) compression rate of the Shannon entropy of the source. In this paper, we consider a quantum extension of above task, where Alice receives a sample from a known probability distribution and needs to transmit a part of a pure quantum state (that is associated with the sample) to Bob. We allow entanglement assistance in the protocol, so that the communication is possible through classical messages, for example using quantum teleportation. The classical messages can have a variable length, and the goal is to minimize their expected length. We provide a characterization of the expected communication cost of this task, by giving a lower bound that is near optimal up to some additive factors. A special case of above task, and the quantum analogue of the source compression problem, is when Alice needs to transmit the whole of her pure quantum state. Here, we show that there is no one-shot interactive scheme which matches the asymptotic and i.i.d. compression rate of the von Neumann entropy of the average quantum state. This is a relatively rare case in the quantum information theory where the cost of a quantum task is significantly different from its classical analogue. Furthermore, we also exhibit similar results for the fully quantum task of quantum state redistribution, employing some different techniques. We show implications for the one-shot version of the problem of quantum channel simulation.