Expected Communication Cost of Distributed Quantum Tasks
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2020
|
| Online Access: | https://hdl.handle.net/1721.1/124013 |
| _version_ | 1826205256521875456 |
|---|---|
| author | Anshu, Anurag Garg, Ankit Harrow, Aram W. Yao, Penghui |
| author2 | Massachusetts Institute of Technology. Center for Theoretical Physics |
| author_facet | Massachusetts Institute of Technology. Center for Theoretical Physics Anshu, Anurag Garg, Ankit Harrow, Aram W. Yao, Penghui |
| author_sort | Anshu, Anurag |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:09:49Z |
| format | Article |
| id | mit-1721.1/124013 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:09:49Z |
| publishDate | 2020 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1240132022-10-01T13:27:55Z Expected Communication Cost of Distributed Quantum Tasks Anshu, Anurag Garg, Ankit Harrow, Aram W. Yao, Penghui Massachusetts Institute of Technology. Center for Theoretical Physics 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. 2020-03-04T20:36:51Z 2020-03-04T20:36:51Z 2018-11 Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 https://hdl.handle.net/1721.1/124013 Anshu, Anurag et al. "Expected Communication Cost of Distributed Quantum Tasks." : IEEE Transactions on Information Theory 64, 11 (November 2018): 7395-7423 © 2018 IEEE 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 10.1109/TIT.2018.2849066 http://dx.doi.org/10.1109/tit.2018.2849066 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Prof. Harrow |
| spellingShingle | Anshu, Anurag Garg, Ankit Harrow, Aram W. Yao, Penghui Expected Communication Cost of Distributed Quantum Tasks |
| title | Expected Communication Cost of Distributed Quantum Tasks |
| title_full | Expected Communication Cost of Distributed Quantum Tasks |
| title_fullStr | Expected Communication Cost of Distributed Quantum Tasks |
| title_full_unstemmed | Expected Communication Cost of Distributed Quantum Tasks |
| title_short | Expected Communication Cost of Distributed Quantum Tasks |
| title_sort | expected communication cost of distributed quantum tasks |
| url | https://hdl.handle.net/1721.1/124013 |
| work_keys_str_mv | AT anshuanurag expectedcommunicationcostofdistributedquantumtasks AT gargankit expectedcommunicationcostofdistributedquantumtasks AT harrowaramw expectedcommunicationcostofdistributedquantumtasks AT yaopenghui expectedcommunicationcostofdistributedquantumtasks |