Programme

Final programme available here: BIID 4 Programme

Talk titles and abstracts: (downloadable pdf file here)

Matthieu Bloch (GeorgiaTech) : Covert communications over noisy channels: partial first and second-order asymptotics (pdf)

In this talk, we will present recent results regarding the information-theoretic limits of covert communication over noisy channels. While covert communications schemes can be built by relying on the known coding mechanisms of channel reliability and channel resolvability, covert communication is only possible in a regime of negligible communication rate. This distinction leads to intriguing technical challenges and results, such as the absence of strong converse in the parameter controlling covertness. We will discuss the first-order and second-order asymptotics of covert communication for point-to-point channels and present extensions to multi-terminal settings.

Patrick Coles (IQC, Waterloo) : Entropic uncertainty relations (pdf)

In this talk, we will review the past, present, and future of entropic uncertainty relations (EURs). This includes (1) an overview of proof techniques for deriving EURs, (2) a discussion of quantum-memory EURs and their role in quantum cryptography, (3) other applications of EURs such as metrology and witnessing of steering and entanglement, (4) the role of EURs in quantum foundations such as measurement uncertainty and wave-particle duality. Finally we will mention some unresolved conjectures and open problems. This talk is related to our review article with Mario Berta, Marco Tomamichel, and Stephanie Wehner (arXiv:1511.04857).

Nilanjana Datta (Cambridge University) : Second-order asymptotics for quantum hypothesis testing in settings beyond i.i.d. (pdf)

Quantum Stein’s Lemma is a cornerstone of quantum statistics and concerns the problem of correctly identifying a quantum state, given the knowledge that it is one of two specific states (ρ or σ). It was originally derived in the asymptotic i.i.d. setting, in which arbitrarily many (say, n) identical copies of the state (ρ^⊗n or σ^⊗n) are considered to be available. In this setting, the lemma states that, for any given upper bound on the probability αn of erroneously inferring the state to be σ, the probability βn of erroneously inferring the state to be ρ decays exponentially in n, with the rate of decay converging to the relative entropy of the two states. The second order asymptotics for quantum hypothesis testing, which establishes the speed of convergence of this rate of decay to its limiting value, was derived in the i.i.d. setting independently by Tomamichel and Hayashi, and Li. We extend this result to settings beyond i.i.d.. Examples of these include Gibbs states of quantum spin systems (with finite-range, translation-invariant interactions) at high temperatures, and quasi-free states of Fermionic lattice gases. This is joint work with Yan Pautrat (Orsay) and Cambyse Rouzé (Cambridge).

Frédéric Dupuis : Entropy accumulation (pdf)

We ask the question whether entropy accumulates, in the sense that the operationally relevant total uncertainty about an n-partite system A = (A1,..., An) corresponds to the sum of the entropies of its parts Ai. The Asymptotic Equipartition Property implies that this is indeed the case to first order in n - under the assumption that the parts Ai are identical and independent of each other. Here we show that entropy accumulation occurs without an independence assumption, provided one quantifies the uncertainty about the individual systems Ai by the von Neumann entropy of suitably chosen conditional states. This has a number of applications in cryptography: for example, it can be used to generically reduce the security of QKD in the general attack, finite-key regime to the case of iid attacks in the asymptotic key regime. It can also be used in the device-independent setting to provide essentially optimal security bounds, as shown in an upcoming paper by Arnon-Friedman, Renner and Vidick.

This is joint work with Omar Fawzi and Renato Renner.

Omar Fawzi (ENS Lyon) : Complexity of optimal channel coding (pdf)

We study the problem of finding the maximum success probability for transmitting messages over a noisy channel from an algorithmic point of view. In particular, we show that a simple greedy polynomial-time algorithm computes a code achieving a (1-1/e)-approximation of the maximum success probability and that it it is NP-hard to obtain an approximation ratio strictly better than (1-1/e). Moreover, the natural linear programming relaxation of this problem corresponds to the Polyanskiy-Poor-Verdú bound, which we also show has a value of at most 1/(1-1/e) times the maximum success probability. Based on joint work with Siddharth Barman arXiv:1508.04095

Gilad Gour (University of Calgary, Alberta) : Local additivity of minimum output entropies (pdf)

One of the major open problems in quantum information concerns with the question whether entanglement between signal states can help to send classical information over quantum channels. Few years ago, Hasting proved that entanglement does help by finding a counter-example for the long standing additivity conjecture that the minimum von-Neumann entropy output of a quantum channel is additive under taking tensor products. In this talk I will show that the minimum von-Neumann entropy output of a quantum channel, as well as all other Rényi entropies with parameter p > 1, are locally additive. The counterexamples for the global additivity conjecture of the Rényi entropies, make this result somewhat surprising. In particular, it indicates that the non-additivity of the minimum entropy output is related to a global effect of quantum channels. I will end with few related open problems.

Saikat Guha (BBN Technologies) : Thinning, photonic beam splitting, and entropy power (pdf)

Shannon's entropy power inequality (EPI) found many uses in coding theorem converses involving Gaussian sources and channels. Many partially-successful attempts have been made to find the most natural discrete-variable version of Shannon's EPI. We develop an axiomatic framework surrounding entropy power, monotonicity and the central limit theorem, from which we deduce a natural form of a discrete-variable EPI and an associated entropic monotonicity in a discrete-variable central limit theorem. In this discrete EPI, the geometric distribution, which has the maximum entropy among all discrete distributions with a given mean, assumes a role analogous to the Gaussian distribution in Shannon's EPI. The entropy power of X is defined as the mean of a geometric random variable with entropy H(X). The crux of our construction is a discrete-variable version of Lieb's scaled addition of two discrete random variables X and Y. We discuss the relationship of our discrete EPI with recent work of Yu and Johnson who developed an EPI for a restricted class of random variables that have ultra-log-concave (ULC) distributions. Even though we leave open the proof of the aforesaid natural form of the discrete EPI, we show that this discrete EPI holds true for variables with arbitrary discrete distributions when the entropy power is redefined as eH(X) in analogy with the continuous version. Finally, we show that our conjectured discrete EPI is a special case of the yet-unproven Entropy Photon-number Inequality (EPnI), which assumes a role analogous to Shannon's EPI in capacity proofs for Gaussian bosonic (quantum) channels.

Alexander Holevo (Steklov Institute, Moscow) : Quantum signal plus noise models: Beyond IID (arXiv)

Recently, the Gaussian optimizer conjecture was confirmed for Bosonic Gaussian gauge-covariant or contravariant channels (Giovannetti, A.H., Garcia-Patrón, arXiv:1312.2251). It was shown that the classical capacity of these channels under the input energy constraint is additive and achieved by Gaussian encodings. These results use the i.i.d. model of the quantum noise. In this talk we consider two quantum Gaussian signal plus noise models with stationary coloured noise. In particular, a proof is given of the coding theorem for a broadband stationary noise model.

Oliver Johnson (University of Bristol) : Finite block length aspects of group testing (pdf)

The group testing problem was introduced by Dorfman in the 1940s, and gives a model for isolating a small number of infected members of a larger population. I will review recent work on this problem, and explain some new algorithms which can be proved to perform well in certain sparsity regimes. To complement this, I will explain how the channel coding argument of Polyanskiy, Poor and Verdú gives a strong converse, by a comparison with a certain statistical hypothesis test. If time permits, I will explain how the adaptive group testing problem (corresponding to channels with feedback) can be analysed in a similar way using directed information.

Anthony Leverrier (INRIA, Paris) : Quantum expander codes (pdf)

We present an efficient decoding algorithm for constant rate quantum hypergraph-product LDPC codes which provably corrects adversarial errors of weight Ω(√n) for codes of length n. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

(Joint work with Jean-Pierre Tillich and Gilles Zémor, arXiv:1504.00822 - FOCS 2015)

Christian Majenz (QMath, University of Copenhagen) : Catalytic Decoupling of Quantum Information (pdf)

The decoupling technique is a fundamental tool in quantum information theory with applications ranging from quantum thermodynamics to quantum many body physics to the study of black hole radiation. In this work we introduce the notion of catalytic decoupling, that is, decoupling in the presence of an uncorrelated ancilla system. This removes a restriction on the standard notion of decoupling, which becomes important for structureless resources, and yields a tight characterization in terms of the max-mutual information allowing for a second order asymptotic expansion of the i.i.d. case. Catalytic decoupling naturally unifies various tasks like the erasure of correlations and quantum state merging.

Iman Marvian (MIT) : The resource theory of asymmetry and quantum reference frames (pdf)

The resource theory of asymmetry is a framework for classifying and quantifying the symmetry-breaking properties of both states and operations relative to a given symmetry. This has been shown to be useful, for instance, for finding the consequences of symmetries of open and closed system dynamics beyond Noether’s theorem. Also, this resource theory naturally arises in the context of quantum reference frames, because the relevant property of a quantum state that determines its usefulness as a quantum reference frame can be understood as its asymmetry relative to a symmetry group. In this talk I present an overview of the resource theory of asymmetry, and discuss some of its applications. In particular, I will argue that this resource theory provides a natural framework to study the notion of coherence which is relevant in the context of quantum metrology and quantum speed limits. Also, I briefly talk about a recent work on "Universal Quantum Emulator", in which the concept of quantum reference frames appears in a new context (Further details on this work are presented in a poster in the poster session).

Janis Noetzel (UAB) : Super-activation as a phenomena in information theory (pdf)

Proving that the phenomenon of super-activation of capacity may occur in information transmission over quantum channels has been one of the celebrated highlights in quantum information theory that was assumed to distinguish it from the classical theory. Our focus in this talk will be on the recent results in classical Shannon information theory (see arXiv:1501.07439), which demonstrate that strict super-activation may occur even in classical information theory, when secure information transmission over arbitrarily varying channels is considered. The idea goes back to a protocol published by Boche and Schaefer (2013). In the work arXiv:1501.07439 we were able to give a complete characterization of the effect, moving way beyond the initial protocol. We will also put these recent results into context with earlier activation results in classical information theory that have shown similar effects, even though no strict super-activation of a capacity was demonstrated there. It will be explained how the arbitrarily varying channel model interpolates between the i.i.d. setting and scenarios where channels act memoryless but where the statistics of the channel may change drastically in between channel uses. A summary of super-activation results in quantum information theory will be given as well.

Giacomo de Palma (Scuola Normale Superiore, Pisa) : Entropy Photon-Number Inequality (pdf)

Gaussian input states have long been conjectured to minimize the output von Neumann entropy of quantum Gaussian channels for fixed input entropy. The corresponding conjectured inequality for the output entropy has been called Entropy Photon-number Inequality (EPnI). We prove the quantum Entropy Power Inequality, that provides an extremely tight lower bound to this minimum output entropy, but is not saturated by Gaussian states, hence it is not sufficient to prove their optimality. The passive states of a quantum system minimize the average energy for a given spectrum. We prove that for any one-mode Gaussian channel, the output generated by a passive state majorizes the output generated by any state with the same spectrum, hence it has a lower entropy. Then, the minimizers of the output entropy of a Gaussian channel for fixed input entropy are passive states. We exploit this result to prove that Gaussian states minimize the output entropy of the one-mode attenuator for fixed input entropy. This result opens the way to the multimode generalization, that permits to determine both the classical capacity region of the Gaussian quantum degraded broadcast channel and the triple trade-off region of the quantum attenuator. The extension of this result to the quantum-limited amplifier permits to determine its triple trade-off region.

Yury Polyanskiy (MIT) : Strong data-processing inequalities for channels and Bayesian networks

The data-processing inequality, that is, I(U;Y) ≤ I(U;X) for a Markov chain U - X - Y, has been the method of choice for proving impossibility (converse) results in information theory and many other disciplines. Various channel-dependent improvements (called strong data-processing inequalities, or SDPIs) of this inequality have been proposed both classically and more recently. In this talk I will survey known results relating various notions of contraction for a single channel. Then we will discuss a basic extension: given an SDPI for each constituent channel in a Bayesian network, how to produce an end-to-end SDPI?

Joseph Renes (ETH Zurich) : Quantum Polar Codes: The uses of complementarity in quantum coding (pdf)

In this talk I'll review the phenomenon of polarization and describe both the standard and a brand new construction of polar codes. I'll also talk about the uses of complementarity to go beyond stabilizer decoding in quantum error-correction, for example to decode codeword stabilized codes and to find efficient polar decoders for non-Pauli channels such as amplitude damping.​

Anelia Somekh-Baruch (Bar-Ilan University, Tel Aviv) : Mismatched decoding (pdf)

The mismatch capacity is the highest achievable rate using a given fixed decoding rule. Mismatched decoding reflects a situation in which due to inaccurate knowledge of the channel, or due to some practical limitations, the receiver is constrained to use the possibly suboptimal decoder. This is a very practical issue in the design of communication systems. Nevertheless, even determining a single-letter expression for the mismatch capacity of the single-user discrete memoryless channel remains an open problem.

In this talk, we will survey previous as well as recent and new results on mismatched decoding; Single-letter characterization of achievable rates and error exponents will be presented for mismatched discrete memoryless channels (DMCs) with an additive metric. Further, multi-letter expressions and bounds for DMCs will be discussed. The fundamental limits of a general channel, defined as a sequence of conditional distributions with a general decoding metrics sequence, will be addressed. Time permitting, we will present results pertaining to mismatched list-decoding.

David Sutter (ETH Zurich) : Multivariate trace inequalities (pdf)

The Golden-Thompson (GT) and the Araki-Lieb-Thirring (ALT) inequality are powerful tools with applications ranging from statistical physics and random matrix theory to quantum information theory. We will present intuitive and transparent proofs for these inequalities based on asymptotic spectral pinching and complex interpolation theory. These proofs immediately suggest extensions of the GT and ALT inequality to arbitrarily many matrices. We will see that our extension of the GT inequality to four matrices can be used to prove remainder terms for the monotonicity of the quantum relative entropy and strong sub-additivity of the von Neumann entropy in terms of recoverability.

Based on joint work with Mario Berta and Marco Tomamichel (arXiv:1604.03023).

Vincent Y. F. Tan (NUS Singapore) : Information-Theoretic Limits of Streaming Communication (pdf)

We consider streaming data transmission over a discrete memoryless channel. A new message is given to the encoder at the beginning of each block and the decoder decodes each message sequentially, after a delay of T blocks. In this streaming setup, we study the fundamental interplay between the rate and error probability in the central limit and moderate deviations regimes and show the following achievability results: i) in the moderate deviations regime, the moderate deviations constant improves over the block coding or non-streaming setup at least by a factor of T and ii) in the central limit regime, the second-order coding rate improves at least by a factor of approximately \sqrt{T} for a wide range of channel parameters. For both the regimes, we propose coding techniques that incorporate a joint encoding of fresh and previous messages. Furthermore, we show that the exponent of the error probability can be improved tremendously by allowing variable decoding delay in the moderate deviations regime.

In addition, we also show how to derive a tight converse result for the moderate deviations regime. For the converse proof, a more powerful decoder to which some extra information is fed forward is assumed. The error probability is bounded first for an auxiliary channel and this result is translated back to the original channel by using a newly developed change-of-measure lemma, where the speed of decay of the remainder term in the exponent is carefully characterized.

This is joint work with Si-Hyeon Lee and Ashish Khisti, both of the University of Toronto. arXiv:1512.06298, arXiv:1604.06848

Shun Watanabe (Tokyo Univ of Agriculture & Technology) : Converses to wiretap channel coding (pdf)

In this talk, we revisit the problem of wiretap channel coding. In particular, our focus of this talk is converse part of this problem. We show a technique to derive a converse bound by relating the wiretap channel coding with a hypothesis testing problem, which leads to the strong converse on the degraded wiretap channel. We also show results on the secret key agreement problem, which is closely related to the wiretap channel. Finally, we also discuss some open problems on the wiretap channel and the secret key agreement. This is a joint work with Masahito Hayashi and Himanshu Tyagi.