Document Open Access Logo

Lower Bound on Expected Communication Cost of Quantum Huffman Coding

Authors Anurag Anshu, Ankit Garg, Aram W. Harrow, Penghui Yao

PDF
Thumbnail PDF

File

LIPIcs.TQC.2016.3.pdf
  • Filesize: 0.54 MB
  • 18 pages

Document Identifiers

Author Details

Anurag Anshu
Ankit Garg
Aram W. Harrow
Penghui Yao

Cite As Get BibTex

Anurag Anshu, Ankit Garg, Aram W. Harrow, and Penghui Yao. Lower Bound on Expected Communication Cost of Quantum Huffman Coding. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.TQC.2016.3

Abstract

Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length.

For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially.

For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of Quantum Reverse Shannon theorem.

Subject Classification

Keywords
  • Quantum information
  • quantum communication
  • expected communica- tion cost
  • huffman coding

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Anurag Anshu. A lower bound on expected communication cost of quantum state redistribution, 2015. URL: http://arxiv.org/abs/1506.06380.
  2. Anurag Anshu, Ankit Garg, Aram Harrow, and Penghui Yao. Lower bound on expected communication cost of quantum huffman coding, 2016. URL: http://arxiv.org/abs/1605.04601.
  3. Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, and Penghui Yao. A new operational interpretation of relative entropy and trace distance between quantum states, 2014. URL: http://arxiv.org/abs/1404.1366.
  4. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Proceedings of the forty-second ACM symposium on Theory of computing, STOC'10, pages 67-76, New York, NY, USA, 2010. ACM. Google Scholar
  5. Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schumacher. Noncommuting mixed states cannot be broadcast. Phys. Rev. Lett., 76:2818-2821, Apr 1996. URL: http://dx.doi.org/10.1103/PhysRevLett.76.2818.
  6. M. Berta, M. Christandl, and D. Touchette. Smooth entropy bounds on one-shot quantum state redistribution. IEEE Transactions on Information Theory, 62(3):1425-1439, March 2016. URL: http://dx.doi.org/10.1109/TIT.2016.2516006.
  7. S. L. Braunstein, C. A. Fuchs, D. Gottesman, and Hoi-Kwong Lo. A quantum analog of huffman coding. In Information Theory, 1998. Proceedings. 1998 IEEE International Symposium on, pages 353-, Aug 1998. URL: http://dx.doi.org/10.1109/ISIT.1998.708958.
  8. Mark Braverman and Anup Rao. Information equals amortized communication. In Proceedings of the 52nd Symposium on Foundations of Computer Science, FOCS'11, pages 748-757, Washington, DC, USA, 2011. IEEE Computer Society. Google Scholar
  9. Igor Devetak and Jon Yard. Exact cost of redistributing multipartite quantum states. Phys. Rev. Lett., 100:230501, Jun 2008. URL: http://dx.doi.org/10.1103/PhysRevLett.100.230501.
  10. M. Fannes. A continuity property of the entropy density for spin lattice systems. Communications in Mathematical Physics, 31:291–294, 1973. Google Scholar
  11. P. Harsha, R. Jain, D. McAllester, and J. Radhakrishnan. The communication complexity of correlation. IEEE Transactions on Information Theory, 56(1):438-449, Jan 2010. URL: http://dx.doi.org/10.1109/TIT.2009.2034824.
  12. Alexander S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problems of Information Transmission, (9):177-183, 1973. Google Scholar
  13. Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Quantum state merging and negative information. Communications in Mathematical Physics, 269:107-136, 2007. URL: http://dx.doi.org/10.1007/s00220-006-0118-x.
  14. David Huffman. A method for the construction of minimum-redundancy codes. Proceedings of IRE, 40(9):1098-1101, 1952. Google Scholar
  15. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and privacy in quantum communication. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 285-296, Washington, DC, USA, 2005. IEEE Computer Society. URL: http://dx.doi.org/10.1109/CCC.2005.24.
  16. Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity, 2008. URL: http://arxiv.org/abs/0807.1267.
  17. Michel Ledoux. The concentration of measure phenomenon. Mathematical Surveys and Monographs. American Mathematical Society, 2005. Google Scholar
  18. G. Lindblad. Completely positive maps and entropy inequalities. Commun. Math. Phys., 40:147-151, 1975. Google Scholar
  19. Claude Elwood Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:379-423, 1948. URL: http://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x.
  20. D. Slepian and J. Wolf. Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 19(4):471-480, Jul 1973. URL: http://dx.doi.org/10.1109/TIT.1973.1055037.
  21. Marco Tomamichel. A framework for non-asymptotic quantum information theory, 2012. PhD Thesis, ETH Zurich. URL: https://arxiv.org/abs/1203.2142.
  22. Dave Touchette. Quantum information complexity. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC'15, pages 317-326, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2746539.2746613.
  23. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, Theory and Applications. Cambridge University Press, 2012. Google Scholar
  24. John Watrous. Theory of Quantum Information, lecture notes, 2011. URL: https://cs.uwaterloo.ca/~watrous/LectureNotes.html.
  25. A. Wyner. The common information of two dependent random variables. IEEE Transactions on Information Theory, 21(2):163-179, Mar 1975. URL: http://dx.doi.org/10.1109/TIT.1975.1055346.
  26. J. T. Yard and I. Devetak. Optimal quantum source coding with quantum side information at the encoder and decoder. IEEE Transactions on Information Theory, 55(11):5339-5351, Nov 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact