skip to content
 

Timetable (MQIW05)

Beyond I.I.D. in information theory

Monday 23rd July 2018 to Friday 27th July 2018

Monday 23rd July 2018
08:50 to 09:25 Registration
09:25 to 09:35 Welcome from Christie Marr (INI Deputy Director)
09:35 to 09:45 Welcome from the organisers
09:45 to 10:30 Renato Renner (ETH Zürich)
Entropy Accumulation: The Theorem and a Conjecture
The Entropy Accumulation Theorem is, roughly speaking, the “Beyond-IID”-version of the Asymptotic Equipartition Property. It asserts that the smooth min-entropy of a system that consists of many parts is well approximated by the sum of the von Neumann entropies of its subsystems (evaluated for suitably chosen states of these subsystems). In my talk, I will revisit this theorem and conjecture a generalisation. The latter would extend the accumulation theorem to quantities other than entropies.



INI 1
10:30 to 11:00 Morning Coffee
11:00 to 11:45 Yiannis Kontoyiannis (University of Cambridge); (Athens University of Economics and Business)
Lossy Compression Coding Theorems for Arbitrary Sources
We give a development of the theory of lossy data compression from the point of view of statistics. This is partly motivated by the enormous success of the statistical approach in lossless compression. A precise characterization of the fundamental limits of compression performance is given, for arbitrary data sources and with respect to general distortion measures. The emphasis is on non-asymptotic results and results that hold with high probability (and not just on the average). The starting point for this development is the observation that there is a precise correspondence between compression algorithms and probability distributions (in analogy with the Kraft inequality in lossless compression). This leads us to formulate a version of the celebrated Minimum Description Length (MDL) principle for lossy data compression. We discuss the consequences of the lossy MDL principle, and we explain how it can lead to practical design lessons for vector quantizer design.
INI 1
11:45 to 12:30 Joe Renes (ETH Zürich)
On privacy amplification, lossy compression, and their duality to channel coding
We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. This formulation can be easily computed to give finite-blocklength bounds and turns out to be equivalent to smooth min-entropy bounds by Renner and Wolf [Asiacrypt 2005] and Watanabe and Hayashi [ISIT 2013], as well as a bound in terms of the E divergence by Yang, Schaefer, and Poor [arXiv:1706.03866 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with known relations between channel simulation and lossy source coding, this implies that privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to protocols of optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [IEEE Trans. Info. Theory 64, 577 (2018)], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.



INI 1
12:30 to 14:00 Buffet Lunch at CMS
14:00 to 14:45 Guangyue Han (University of Hong Kong)
Information-Theoretic Extensions of the Shannon-Nyquist Sampling Theorem
This talk will present information-theoretic extensions of the classical Shannon-Nyquist sampling theorem and some of their applications. More specifically, we consider a continuous-time white Gaussian channel, which is typically formulated using a white Gaussian noise. A conventional way for examining such a channel is the sampling approach based on the Shannon-Nyquist sampling theorem, where the original continuous-time channel is converted to an equivalent discrete-time channel, to which a great variety of established tools and methodology can be applied. However, one of the key issues of this scheme is that continuous-time feedback and memory cannot be incorporated into the channel model. It turns out that this issue can be circumvented by considering the Brownian motion formulation of a continuous-time white Gaussian channel. Nevertheless, as opposed to the white Gaussian noise formulation, a link that establishes the information-theoretic connection between a continuous -time channel under the Brownian motion formulation and its discrete-time counterparts has long been missing. This paper is to fill this gap by establishing causality-preserving connections between continuous-time Gaussian feedback/memory channels and their associated discrete-time versions in the forms of sampling and approximation theorems, which we believe will help to contribute the further development of continuous-time information theory.

Related Links
INI 1
14:45 to 15:30 Young-Han Kim (University of California, San Diego)
Shannon theory of ergodic sources and channels
Many interesting source and channel models have memory. When the temporal dependence fades away sufficiently fast (or more precisely, if the source or noise process is ergodic), the standard coding techniques developed in classical Shannon theory can be extended beyond i.i.d. memoryless cases, resulting in limiting expressions for rate--distortion and capacity. The key idea behind this extension is the ergodic decomposition of stationary processes, which was utilized earlier by Gallager for rate--distortion theory of ergodic sources and by Kim for capacity of ergodic channels with or without capacity. Such interplay between information theory and ergodic theory is expected to play an important role in problems other than point-to-point source and channel coding. Some technical background can be found in



INI 1
15:30 to 16:00 Afternoon Tea
16:00 to 16:45 René Schwonnek (Universität Hannover)
Additivity of entropic uncertainty relations
We consider the uncertainty between two pairs of local projective measurements performed on a multipartite system. We show that the optimal bound in any linear uncertainty relation, formulated in terms of the Shannon entropy, is additive. This directly implies, against naive intuition, that the minimal entropic uncertainty can always be realized by fully separable states. Hence, in contradiction to proposals by other authors, no entanglement witness can be constructed solely by comparing the attainable uncertainties of entangled and separable states. However, our result gives rise to a huge simplification for computing global uncertainty bounds as they now can be deduced from local ones. Furthermore, we provide the natural generalization of the Maassen and Uffink inequality for linear uncertainty relations with arbitrary positive coefficients.



INI 1
16:45 to 17:30 Zahra Baghali Khanian (Universitat Autònoma de Barcelona)
Compression of correlated quantum-classical sources, or: the price of ignorance
We resume the investigation of the problem of  independent local compression of correlated quantum sources,  the classical case of which is covered by the celebrated  Slepian-Wolf theorem. We focus specifically on quantum-classical (qc) sources,  for which one point of the rate region was previously  determined by Devetak and Winter. Whereas the Devetak- Winter point attains a rate-sum equal to the von Neumann  entropy of the joint source, here we show that the full rate region is much more complex due to the quantum nature of  one of the sources. In particular, we determine the full  rate region in the generic case, showing that all other  points in the achievable region have a rate sum strictly  larger than the joint entropy. We can interpret the difference  as the price paid for the quantum encoder being ignorant  of the classical side information. In the general case, we  give an achievable rate region, via protocols that are built  on the decoupling principle, state merging and state  redistribution. It is matched almost by a single-letter,  but still asymptotic, converse.




INI 1
Tuesday 24th July 2018
09:00 to 09:45 Tobias Koch (Universidad Carlos III de Madrid)
Rényi’s Information Dimension Beyond I.I.D.
Co-author: Bernhard C. Geiger (Graz University of Technology)

In 1959, Rényi proposed the information dimension and the d-dimensional entropy to measure the information content of general random variables. Since then, it was shown that the information dimension is of relevance in various areas of information theory, including rate-distortion theory, almost lossless analog compression, or the analysis of interference channels. In this talk, I will propose a generalization of information dimension to stochastic processes, termed information dimension rate. I will then discuss some of its properties and compare it with other generalizations of information dimension available in the literature. I will further show that for Gaussian processes the information dimension rate permits a simple and intuitive characterization in terms of its spectral distribution function.Joint work with Bernhard Geiger (Graz University of Technology).

Related Links
INI 1
09:45 to 10:30 Ramji Venkataramanan (University of Cambridge)
Strong converses and high-dimensional statistical estimation problems
In many statistical inference problems, we wish to bound the performance of any possible estimator. This can be seen as a converse result, in a standard information-theoretic sense. A standard approach in the statistical literature is based on Fano’s inequality, which typically gives a weak converse. We adapt these arguments by replacing Fano by more recent information-theoretic ideas, based on the work of Polyanskiy, Poor and Verdu. This gives tighter lower bounds that can be easily computed and are asymptotically sharp. We illustrate our technique in three applications: density estimation, active learning of a binary classifier, and compressed sensing, obtaining tighter risk lower bounds in each case.  

(joint with Oliver Johnson, see doi:10.1214/18-EJS14)





INI 1
10:30 to 11:00 Morning Coffee
11:00 to 11:45 Philippe Faist (CALTECH (California Institute of Technology))
Thermodynamic capacity of quantum processes
Thermodynamics imposes restrictions on what state transformations are possible. In the macroscopic limit of asymptotically many independent copies of a state—as for instance in the case of an ideal gas—the possible transformations become reversible and are fully characterized by the free energy. Here, we present a thermodynamic resource theory for quantum processes that also becomes reversible in the macroscopic limit. Namely, we identify a unique single-letter and additive quantity, the thermodynamic capacity, that characterizes the “thermodynamic value” of a quantum channel. As a consequence the work required to simulate many repetitions of a quantum process employing many repetitions of another quantum process becomes equal to the difference of the respective thermodynamic capacities. For our proof, we construct an explicit universal implementation of any quantum process using Gibbs-preserving maps and a battery, requiring an amount of work asymptotically equal to the thermodynamic capacity. This implementation is also possible with thermal operations in the case of time-covariant quantum processes or when restricting to independent and identical inputs. In our derivations we make extensive use of Schur-Weyl duality and information-theoretic routines, leading to a generalized notion of quantum typical subspaces. [joint work with Mario Berta and Fernando Brandão]
INI 1
11:45 to 12:30 Kun Fang (University of Technology Sydney)
Quantum Channel Simulation and the Channel's Smooth Max-Information
Co-authors: Xin Wang (Centre for Quantum Software and Information, University of Technology Sydney), Marco Tomamichel (Centre for Quantum Software and Information, University of Technology Sydney), Mario Berta (Department of Computing, Imperial College London)

We study the general framework of quantum channel simulation, that is, the ability of a quantum channel to simulate another one using different classes of codes. First, we show that the minimum error of simulation and the one-shot quantum simulation cost under no-signalling assisted codes are efficiently computable via semidefinite programming. Second, we introduce the channel's smooth max-information, which can be seen as a one-shot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel's smooth max-information as the one-shot quantum simulation cost. Third, we derive the asymptotic equipartition property (AEP) of the channel's smooth max-information, i.e., it converges to the quantum mutual information of the channel in the independent and identically distributed asymptotic limit. This implies the quantum reverse Shannon theorem (QRST) in the presence of no-signalling correlations. Finally, we explore finite blocklength simulation cost of fundamental quantum channels and provide both numerical and analytical solutions.
INI 1
12:30 to 14:00 Buffet Lunch at CMS
14:00 to 15:00 Open Problem Session INI 1
15:00 to 15:30 Afternoon Tea
15:30 to 17:30 Poster Session
17:30 to 18:30 Welcome Wine Reception at INI
Wednesday 25th July 2018
09:00 to 09:45 Iman Marvian (Duke University)
Coherence distillation machines are impossible in quantum thermodynamics
The role of coherence in quantum thermodynamics has been extensively studied in the recent years and it is now well-understood that coherence between different energy eigenstates is a resource independent of other thermodynamics resources, such as work. A fundamental remaining open question is whether the laws of quantum mechanics and thermodynamics allow the existence a "coherence distillation machine", i.e. a machine that, by possibly consuming work, obtains pure coherent states from mixed states, at a nonzero rate. This question is related to another fundamental question: Starting from many copies of noisy quantum clocks which are (approximately) synchronized with a reference clock, can we distill synchronized clocks in pure states, at a non-zero rate? In this paper we study quantities called "coherence cost" and "distillable coherence", which determine the rate of conversion of coherence in a standard pure state to general mixed states, and vice versa, in the context of quantum thermodynamics. We find that the coherence cost of any state (pure or mixed) is determined by its Quantum Fisher Information (QFI), thereby revealing a novel operational interpretation of this central quantity of quantum metrology. On the other hand, we show that, surprisingly, distillable coherence is zero for typical (full-rank) mixed states. Hence, we establish the impossibility of coherence distillation machines in quantum thermodynamics, which can be compared with the impossibility of perpetual motion machines or cloning machines. To establish this result, we introduce a new additive quantifier of coherence, called the "purity of coherence", and argue that its relation with QFI is analogous to the relation between the free and total energies in thermodynamics.



INI 1
09:45 to 10:30 Gerardo Adesso (University of Nottingham)
Gaussian quantum resource theories
Co-authors: Ludovico Lami (University of Nottingham), Bartosz Regula (University of Nottingham), Xin Wang (University of Technology Sydney), Rosanna Nichols (University of Nottingham), Andreas Winter (Universitat Autonoma de Barcelona)

We develop a general framework characterizing the structure and properties of quantum resource theories for continuous-variable Gaussian states and Gaussian operations, establishing methods for their description and quantification. We show in particular that, under a few intuitive and physically-motivated assumptions on the set of free states, no Gaussian quantum resource can be distilled with free Gaussian operations, even when an unlimited supply of the resource state is available. This places fundamental constraints on state transformations in all such Gaussian resource theories. We discuss in particular the applications to quantum entanglement, where we extend previously known results by showing that Gaussian entanglement cannot be distilled even with Gaussian operations preserving the positivity of the partial transpose, as well as to other Gaussian resources such as steering and optical nonclassicality. A unified semidefinite programming representation of all these reso urces is provided.

Related Links
INI 1
10:30 to 11:00 Morning Coffee
11:00 to 11:45 Zi-Wen Liu (Massachusetts Institute of Technology)
Resource theory of quantum channels
INI 1
11:45 to 12:30 Mischa Woods (ETH Zürich)
The resource theoretic paradigm of Quantum Thermodynamics with Control
The resource theory of quantum thermodynamics has been a very successful theory and has generated much follow up work in the community. It requires energy preserving unitary operations to be implemented over a system, bath, and catalyst as part of its paradigm. So far, such unitary operations have been considered a “free” resource of the theory. However, this is only an idealisation of a necessarily inexact process. Here, we include an additional auxiliary control system which can autonomously implement the unitary by turning “on/off” an interaction. However, the control system will inevitable be degraded by the back-action caused by the implementation of the unitary, which cannot be perfectly implemented. We derive limitations on the quality of the control devise so that the laws of thermodynamics do not change; and prove that the laws of quantum mechanics allow for a sufficiently small back-reaction so that the implementation of thermodynamic resource theoretic operations can be achieved without changing the paradigm, in addition to finding limitations for others.



INI 1
12:30 to 14:00 Buffet Lunch at CMS
14:00 to 17:00 Free Afternoon
Thursday 26th July 2018
09:00 to 09:45 Pranab Sen (Tata Institute of Fundamental Research)
Unions, intersections and a one shot quantum joint typicality lemma
A fundamental tool to prove inner bounds in classical network information theory is the so-called `conditional joint typicality lemma'. In addition to the lemma, one often uses unions and intersections of typical sets in the inner bound arguments without so much as giving them a second thought. These arguments fail spectacularly in the quantum setting. This bottleneck shows up in the fact that so-called `simultaneous decoders', as opposed to `successive cancellation decoders', are known for very few channels in quantum network information theory.

In this talk we shall see how to overcome the bottleneck by proving for the first time a one-shot quantum joint typicality lemma with robust union and intersection properties. To do so we develop two novel tools  in quantum information theory, which we call tilting and smoothing, which should be of independent interest.

Our joint typicality lemma allows us to construct simultaneous quantum decoders for many multiterminal quantum channels and gives a  powerful tool to extend many results in classical network information theory to the one-shot quantum setting. We shall see a glimpse of this in the talk by constructing a one shot simultaneous decoder for the quantum multiple access channel with an arbitrary number of senders. Our one
shot rates reduce to the known optimal rates when restricted to the asymptotic iid setting, which were previously obtained by successive cancellation and time sharing.




INI 1
09:45 to 10:30 Oliver Johnson (University of Bristol)
Some entropy properties of discrete random variables
It is well-known that Gaussian random variables have many attractive properties: they are maximum entropy, they are stable under addition and scaling, they give equality in the Entropy Power Inequality (and hence give sharp log-Sobolev inequalities) and have good entropy concavity properties. I will discuss the extent to which results of this kind can be formulated for discrete random variables, and how they relate to ideas of discrete log-concavity.




INI 1
10:30 to 11:00 Morning Coffee
11:00 to 11:45 Mario Berta (Imperial College London)
Partially smoothed information measures
Smooth entropies are a tool for quantifying resource trade-offs in (quantum) information theory and cryptography. In typical bi- and multi-partite problems, however, some of the sub-systems are often left unchanged and this is not reflected by the standard smoothing of information measures over a ball of close states. We propose to smooth instead only over a ball of close states which also have some of the reduced states on the relevant sub-systems fixed. This partial smoothing of information measures naturally allows to give more refined characterizations of various information-theoretic problems in the one-shot setting. In particular, we immediately get asymptotic second-order characterizations for tasks such as privacy amplification against classical side information or classical state splitting. For quantum problems like state merging the general resource trade-off is tightly characterized by partially smoothed information measures as well. However, for quantum systems we can so far only give the asymptotic first-order expansion of these quantities.
INI 1
11:45 to 12:30 Felix Leditzky (University of Colorado)
Dephrasure channel and superadditivity of coherent information
The quantum capacity of a quantum channel captures its capability for noiseless quantum communication. It lies at the heart of quantum information theory. Unfortunately, our poor understanding of nonadditivity of coherent information makes it hard to understand the quantum capacity of all but very special channels. In this paper, we consider the dephrasure channel, which is the concatenation of a dephasing channel and an erasure channel. This very simple channel displays remarkably rich and exotic properties: we find nonadditivity of coherent information at the two-letter level, a substantial gap between the threshold for zero quantum capacity and zero single-letter coherent information, a big gap between single-letter coherent and private informations. Its clean form simplifies the evaluation of coherent information substantially and, as such, we hope that the dephrasure channel will provide a much-needed laboratory for the testing of new ideas about nonadditivity.



INI 1
12:30 to 14:00 Buffet Lunch at CMS
13:55 to 17:30 Afternoon Session: In memory of Dénes Petz (1953-2018) INI 1
14:00 to 14:45 Milan Mosonyi (Budapest University of Technology and Economics)
Dénes Petz' legacy in quantum information theory
In this talk we give an overview of a subjective selection of Dénes Petz's many results on quantum entropies and their impact on quantum information theory, with a special emphasis on recent results inspired by them.



INI 1
14:45 to 15:30 Fumio Hiai (Tohoku University)
Quantum f-divergences in von Neumann algebras
This talk is a comprehensive survey on recent developments of quantum divergences in general von Neumann algebras, including standard f-divergences, maximal f-divergences, and R\'enyi type divergences, whose mathematical backgrounds are Haagerup's L^p-spaces and Araki's relative modular operator. Standard f-divergences were formerly studied by Petz in a bit more general form with name quasi-entropy, whose most familiar one is the relative entropy initiated by Umegaki and extended to general von Neumann algebras by Araki. We extend Kosaki's variational expression of the relative entropy to an arbitrary standard f-divergence, from which most important properties of standard f-divergences follow immediately. We also go into standard R\'enyi divergences (as a variation of standard f-divergences) in some detail, and touch briefly sandwiched R\'enyi divergences in von Neumann algebras, which have recently been developed by Jen\v cov\'a and Berta-Scholz-Tomamichel. Finally, we treat maximal f-divergences and discuss their definition, integral expression, and comparison with standard f-divergences. This talk is dedicated to the memory of D\'enes Petz.
INI 1
15:30 to 16:00 Afternoon Tea
16:00 to 16:45 Anna Jenčová (Slovak Academy of Sciences)
Renyi relative entropies and noncommutative L_p-spaces
The standard quantum Renyi relative entropies belong to the class of Petz quantum f-divergences and have a number of applications in quantum information theory, including and operational interpretation as error exponents in quantum hypothesis testing. In the last couple of years, the sandwiched version of Renyi relative entropies gained attention for their applications in various strong converse results. While the Petz f-divergences are defined for arbitrary von Neumann algebras, the sandwiched version was introduced for density matrices. In this contribution, it is shown that these quantities can be extended to infinite dimensions. To this end, we use the interpolating family of non-commutative L_p-spaces with respect to a state, defined by Kosaki. This definition provides us with tools for proving a number of properties of the sandwiched Renyi entropies, in particular the data processing inequality with respect to normal unital (completely) positive maps. It is also shown that this definition coincides with the previously introduced Araki-Masuda divergences by Berta et. al.

The notion of sufficient (or reversible) quantum channels was introduced and studied by Petz. One of the fundamental results in this context is the fact that equality in the data processing inequality for the quantum relative entropy is equivalent to sufficiency of the channel. We extend this result for sandwiched Renyi relative entropies. See arXiv:1609.08462 and arXiv:1707.00047 for more details.
INI 1
16:45 to 17:30 Beth Ruskai (University of Massachusetts Lowell)
Using local additivity to find examples of superadditivity of quantum channels
The local additivity of minimal output entropy can be extended to local additivity of maximal relative entropy with respect to a fixed reference state. This can be exploited to test channels for superadditivity of Holevo capacity with numerical effort comparable to searching for the minimal output entropy. Local maxima which do not arise from product inputs play a key role.  Moreover, evidence of superadditivity can be found even if the additivity violation itself is too small to be seen numerically.  A  max-min expression for the capacity, dues to Petz, et al, plays a key role.



INI 1
19:00 to 22:00 Formal Dinner at Pembroke College (Old Library)
Friday 27th July 2018
09:00 to 09:45 Ivan Bardet (Institut Henri Poincaré)
Functional inequalities and the study of the speed of decoherence of an open quantum system
INI 1
09:45 to 10:30 Sergii Strelchuk (University of Cambridge)
Classical and quantum features of Schur transform for information processing
It is well-known that Gaussian random variables have many attractive properties: they are maximum entropy, they are stable under addition and scaling, they give equality in the Entropy Power Inequality (and hence give sharp log-Sobolev inequalities) and have good entropy concavity properties. I will discuss the extent to which results of this kind can be formulated for discrete random variables, and how they relate to ideas of discrete log-concavity.




INI 1
10:30 to 11:00 Morning Coffee
11:00 to 11:45 Cambyse Rouzé (Mathematics, University of Cambridge)
Quantum reverse hypercontractivity: its tensorization and application to strong converses
Hypercontractivity and log-Sobolev inequalities have found interesting applications in information theory in the past few years. In particular, recently a strong converse bound for the hypothesis testing problem have been proven based on the reverse hypercontractivity inequalities. This talk is about the generalization of this application to the quantum setting. First, the theory of quantum reverse hypercontractivity and its equivalence with the log-Sobolev inequalities will be discussed. To this end, the problem of the tensorization of quantum hypercontractivity inequalities will be addressed. Next, it is shown how quantum reverse hypercontractivity inequalities can be used for proving strong converse bounds in the quantum setting.



INI 1
11:45 to 12:30 Ángela Capel (ICMAT)
Quantum Conditional Relative Entropy and Quasi-Factorization of the relative entropy
The existence of a positive log-Sobolev constant implies a bound on the mixing time of a quantum dissipative evolution under the Markov approximation. For classical spin systems, such constant was proven to exist, under the assumption of a mixing condition in the Gibbs measure associated to their dynamics, via a quasi-factorization of the entropy in terms of the conditional entropy in some sub--algebras.

In this work we analyze analogous quasi-factorization results in the quantum case. For that, we dene the quantum conditional relative entropy and prove several quasi-factorization results for it. As an illustration of their potential, we use one of them to obtain a positive log-Sobolev constant for the heat-bath dynamics with product fixed point.



INI 1
12:30 to 13:15 Marius Junge (University of Illinois); (University of Illinois at Urbana-Champaign)
Relative Entropy and Fisher Information
We show that in finite dimension the set of generates satisfying a stable version of the log-sobolev inequality for the Fisher information is dense. The results is based on  a new algebraic property , valid for subordinates semigroups  for sublabplacians  on compact Riemann manifolds which is then transferred to matrix algebras. Even in the commutative setting the inequalities for subordinated sublaplacians are entirely new. We also found counterexample for why a naive approach via hypercontractivity is not expected to work in a matrix-valued setting, similar  to results by Bardet and collaborators.



INI 1
13:15 to 15:15 Buffet Lunch at CMS
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons