License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2016.3
URN: urn:nbn:de:0030-drops-66843
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6684/
Go to the corresponding LIPIcs Volume Portal

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

Lower Bound on Expected Communication Cost of Quantum Huffman Coding

pdf-format:
LIPIcs-TQC-2016-3.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{anshu_et_al:LIPIcs:2016:6684,
  author =	{Anurag Anshu and Ankit Garg and Aram W. Harrow and Penghui Yao},
  title =	{{Lower Bound on Expected Communication Cost of Quantum Huffman Coding}},
  booktitle =	{11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-019-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{61},
  editor =	{Anne Broadbent},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6684},
  URN =		{urn:nbn:de:0030-drops-66843},
  doi =		{10.4230/LIPIcs.TQC.2016.3},
  annote =	{Keywords: Quantum information, quantum communication, expected communica- tion cost, huffman coding}
}

Keywords: Quantum information, quantum communication, expected communica- tion cost, huffman coding
Collection: 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Issue Date: 2016
Date of publication: 22.09.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI