Beyond I.I.D. in Information Theory (15w5120)

Arriving in Banff, Alberta Sunday, July 5 and departing Friday July 10, 2015


Nilanjana Datta (Cambridge University)

Renato Renner (ETH Zurich)

(Louisiana State University, Baton Rouge)

(Universitat Autonoma de Barcelona)


Quantum Shannon theory is arguably the core of the new “physics of information,” which has revolutionized our understanding of information processing by demonstrating new possibilities that cannot occur in a classical theory of information. The origins of quantum Shannon theory lie in the 1960s, with a slow development until the 1990s when the subject exploded; the last 10-15 years have seen a plethora of new results and methods. Two of the most striking recent discoveries are (1) that entanglement between inputs to successive channel uses can enhance the capacity of a quantum channel for transmitting classical data, and (2) that it is possible for two quantum communication channels to have a non-zero capacity for transmitting quantum data, even if each channel on its own has no such quantum capacity.Crucially, capacity is an asymptotic concept, attained only in the limit of infinitely many uses of the resource. It is natural to ask what happens in settings where only some finite, possibly small number of instances is available, in the extreme case only one. This point of view became central to Renner’s work starting in about 2005, and it blossomed into one-shot (quantum) information theory since, going far beyond the initial field of application to cryptography, but transforming quantum Shannon theory and already finding applications further afield, such as Fernando Brandao and Michal Horodecki’s recent work on area laws in 1D quantum spin systems. Furthermore, this approach might lead to an improved understanding of the above quantum effects.On the proposed subject there have been just a few meetings previously. In fact, the only past one fully dedicated to the same area was the workshop “Beyond i.i.d. in information theory” organized by two of us (N. Datta and R. Renner) in Cambridge, UK, 8-11 January 2013. In the planning is a follow-up workshop next year in Singapore, 21-23 May 2014 (organized by Marco Tomamichel at the Centre for Quantum Technologies). Given the high interest in the subject demonstrated recently, in 2015, a third meeting will be extremely timely. This may be the appropriate point to recall that previous BIRS workshops on quantum information theory focused rather widely on quantum information theory (September 2004), or more specifically on the intersection of quantum information theory with operator algebra (February 2007 and February 2012).We strongly believe that having such a workshop will be timely, and as evidence for this, we can point to some direct results of the “Beyond i.i.d. in information theory” workshop held in Cambridge, UK, that have advanced the field of quantum information theory.At the Cambridge workshop, Serge Fehr introduced a new definition for the Renyi relative entropy, which is now known as the “sandwiched Renyi relative entropy” or “quantum Renyi divergence.” This new Renyi relative entropy is parametrized by a non-negative real number (like the original one) but differs from the original one for any two quantum states represented by non-commutative density operators. Interestingly, Frederic Dupuis and Marco Tomamichel had independently developed the same definition. So after Fehr’s presentation, Dupuis and Tomamichel met with him, and they decided to join efforts to explore properties of this quantity. Meanwhile, Wilde, Winter, and Yang independently realized that the same definition of Renyi relative entropy found a major application in a proof that a strong converse theorem holds for the classical capacity of entanglement-breaking and quantum Hadamard channels. (They were in part influenced to develop strong converse theorems since there were a number of presentations on this topic at the Cambridge workshop.) Since this initial work appeared on the arXiv, there have been many subsequent developments regarding this quantity. In particular, Rupert Frank and Elliott Lieb proved that the new relative entropy is monotone under quantum operations for all values of the parameter between $frac12$ and infinity. (Monotonicity under quantum operations is arguably the most important property that establishes a given quantity as an information measure.) Concurrently, Salman Beigi produced a proof that it is monotone for all values of the parameter between one and infinity, using a completely different approach to do so. Finally, Nilanjana Datta and Felix Leditzky elucidated the (im-)possibility of obtaining the well-known 0-Renyi relative entropy from the new one, and Milan Mosonyi and Tomohiro Ogawa showed how this quantity has an application in establishing a tight strong converse theorem in quantum hypothesis testing. Another line of research that arose as a direct result of the Cambridge workshop is the theory of one-shot quantum rate distortion coding, which describes how well one can compress a quantum data source if allowing for it to incur some distortion after it is reproduced. Such a theory is essential for understanding the compressibility of quantum information in the most general regime. The development of this topic was a direct result of Datta, Renes, Renner, and Wilde attending Victoria Kostina and Sergio Verdu's presentations on classical one-shot rate-distortion coding. Just after their presentations, Datta suggested that it would be worthwhile to employ some of the ideas from the classical realm in developing a quantum theory of one-shot rate distortion coding. This theory makes use of recently developed hypothesis testing entropies and one-shot mutual information quantities, which were also presented at the same Cambridge workshop. The Cambridge workshop was also an opportunity for classical information theorist Sergio Verdu and quantum information theorists Masahito Hayashi, Will Matthews, and Marco Tomamichel to interact. In particular, Polyanskiy, Poor, Verdu, and Hayashi were some of the leading developers of the finite blocklength approach to information theory in the classical domain, and Hayashi, Matthews, and Tomamichel have produced important early work on this topic in the quantum domain. Furthermore, Matthews developed linear programs to establish a converse theorem of Polyanskiy, Poor, and Verdu via non-signalling codes, and Polyanskiy has now extended this work further in the classical domain. One of the major goals of the proposed workshop at BIRS is to increase the interaction between experts on finite blocklength methods in the classical domain and experts in quantum information theory, in order to enhance the activity in this important area in the quantum domain. Another goal of the proposed BIRS workshop is to make substantial progress on several pressing open questions. We list several of these below:We have not yet settled on a one-shot quantity for mutual information or conditional mutual information. As the von Neumann unconditional and conditional mutual information are critical to our understanding of asymptotic quantum information theory, it is essential to understand them from the one-shot perspective. More generally, it is still open to determine the correct quantities in the one-shot domain, and one potential way to settle this question (proposed by Tomamichel at the Cambridge workshop) is to characterize the second-order coding rate for the i.i.d. case in order to see which quantities emerge as better characterizations. It is however unlikely that there will be a unique quantity serving all purposes.In spite of the progress mentioned above, the theory of one-shot rate distortion coding is still in its infancy. In the classical domain, Kostina and Verdu established that the so-called “tilted-information” serves well for characterizing the second-order coding rate in rate distortion coding. It is not clear what the right quantum analogue of this quantity should be, but perhaps by finding it, we would be able to give a better characterization of finite blocklength quantum rate distortion coding, and thus understand the ultimate compressibility of quantum information.Recently, there has been a flurry of activity on generalized divergences, both out of intrinsic interest and due to potential applications in hypothesis testing and channel coding. There is still more work to do, in particular, to understand which Renyi relative entropy is the “correct” one, if indeed there is a single one. Note that we already know that depending on the question at hand different quantities apply, although they all reduce to the same function in the classical case.Are the strong converse bounds established using Renyi-entropic approaches tight? That is, is there a coding scheme that can achieve these upper bounds? An answer either way would be interesting, because either we would find that they are indeed tight or that there might be room for improvement. So far, we have seen that many channels for which the Holevo quantity is additive also obey a strong converse theorem. What is the nature of the relationship between additivity and strong converse theorems? For example, could it be possible to prove the existence of a memoryless channel that does not obey a strong converse theorem by appealing to Hastings' counterexample to additivity?The second order characterization for entanglement-assisted channel coding is still open, despite important recent progress by Matthews and Wehner. The relevance of this question is fundamental: we have understood so far that the entanglement-assisted classical capacity is most analogous to Shannon's channel capacity theorem in many different ways (the formula for it is single-letter and does not increase under a noiseless quantum feedback channel due to results of Bowen), so we would expect its second-order characterization to be well behaved also. Channels with memory are a major challenge both in classical and quantum information theory. This is an area where one-shot techniques could come into their own, as they provide a general framework for dealing with channels without structure. The study of quantum information theory beyond the traditional asymptotic i.i.d. setting is one of the most active areas of research in theoretical quantum information science. Furthermore, it is important for quantum information theorists with expertise in this area and classical information theorists to have opportunities to interact with each other. The Cambridge workshop from January 2013 has had a lasting impact on the field of quantum information theory and we strongly believe that a BIRS workshop on this topic will as well. We are not aware of any other workshops or conferences being held in 2015 on this topic (although there are at least two proposals touching upon quantum information but with no overlap whatsoever with our objectives).