Beyondiid 2014 - Scientific Program

Program

18 May, Sun
19:30 Welcome Reception
19 May, Mon Session Chairs: Marco Tomamichel (Morning), Vincent Tan (Afternoon)
08:45 Registration
08:55 Opening address by Marco Tomamichel, CQT, NUS
09:00 Mark M. Wilde (Louisiana State University, Baton Rouge)
Quantum Information Theory: I.I.D. and Beyond
Arrow Abstract

The field of quantum information theory has rapidly advanced in the past two decades, especially after Shor's discovery of the quantum factoring algorithm and the onset of the quantum computing era. Even decades before this, the early work of Holevo, Helstrom, Lieb, and Ruskai established some basic principles which have shaped the way that quantum information theorists reason about nearly every problem that they tackle. The present talk will give a broad overview of quantum information theory, with the intention for it to be an entry point for classically-trained information theorists and also a review for the experts. As such, we will recall many of the basic important tasks in quantum information theory, beginning with quantum data compression and going on to classical communication, private classical communication, quantum communication, and entanglement-assisted communication over noisy quantum channels. We will focus on the i.i.d. setting for each task and advance to one-shot results and second-order characterizations in settings for which they are known. Another focus of this talk will be to point to open questions of current interest.

| PDF Presentation
10:00 Coffee/Tea Break
10:30 Joseph Renes (ETH Zürich)
What Is Quantum Information?
Arrow Abstract

Classical information is "about something", as in the mutual information I(X:Y) is the information Y has about X. But quantum information? What does it mean, exactly, to have "quantum information" about something? Can we have (classical) information "about" something quantum? This talk will make the case for regarding quantum information as an amalgam of two kinds of classical information: classical information about complementary observables. I will survey how this approach can be useful in constructing quantum and classical information processing protocols both in the iid setting and beyond. For instance, coding techniques from classical information theory can be imported (sometimes wholesale) into the quantum setting, while classical packing problems can be transformed into classical covering problems and vice versa. In this approach one has to constantly be on guard not to run afoul of quantum complementarity, and I will specifically discuss new operationally-motivated uncertainty relations that have been discovered as a result.

| PDF Presentation
11:10 Salman Beigi (Institute for Research in Fundamental Sciences, Tehran)
Quantum Achievability Proof via Collision Relative Entropy
Arrow Abstract

This talk is about a simple framework for deriving one-shot achievable bounds for some problems in quantum information theory. This framework is based on the joint convexity of the exponential of the collision relative entropy, and is a (partial) quantum generalization of the technique of Yassaee et al. (2013) from classical information theory. Based on this framework, some one-shot achievable bounds for the problems of communication over classical-quantum channels, quantum hypothesis testing, and classical data compression with quantum side information are derived. Using the method of information spectrum, I will argue that these one-shot achievable bounds give the asymptotic achievable rates of these problems even up to the second order.

| PDF Presentation
11:50 Omar Fawzi (ETH Zürich)
Testing knowledge in an adversarial setting
Arrow Abstract

Consider a string X of n bits representing some information, and a student holding a general system B representing his knowledge. It is quite intuitive that if the student is able answer correctly an exam, i.e., a randomly chosen subset of the bits of X, then the system B he holds should allow him to reproduce all of X. This talk is about formalizing such a statement when the strategy of the student is completely general. After modelling the setting and describing the desired statement, we will see that for a “memoryless” strategy of the student, proving such a statement is easy. But I will then show that in fact such a statement can be made in general without this assumption. I will give a sketch of the proof when the student holds a classical system. Then, I will highlight some of the difficulties encountered when the student is allowed to have a general quantum system.
This is based on joint work with Normand Beaudry and Renato Renner.

| PDF Presentation
12:25 Lunch-break
13:45 Sergio Verdú (Princeton University)
Converses in Shannon Theory
Arrow Abstract

Converse results give performance guarantees that must be satisfied by every code. The talk will include a survey of converse methods in (classical) data compression and data transmission including some recent results. Single shot methods whose applicability goes beyond iid will receive special focus.

PDF Presentation
14:45 Coffee/Tea Break
15:15 William Matthews (University of Cambridge)
Quantum non-signalling codes and the metaconverse approach
Arrow Abstract

Duan and Winter recently investigated the zero-error performance of "quantum non-signalling codes". I will discuss how the quantum "metaconverse" (or "generalised divergence") approach applies to such codes (for general error probabilities) and show a close relationship between the quantum "hypothesis testing" converse and quantum non-signalling codes which generalises the relationship known in the classical case (see arXiv:1109.5417 and DOI:10.1109/TIT.2012.2236382) I will also discuss the surprising ability of "PPT-preserving" non-signalling codes to send quantum information perfectly over channels of no quantum capacity .
This talk is on joint work with Debbie Leung (IQC).

| PDF Presentation
15:55 Albert Guillen i Fabregas (Universitat Pompeu Fabra, Barcelona)
Error probability and hypothesis testing
Arrow Abstract

This talk will review an expression of the error probability of an arbitrary code as a hypothesis testing problem. In particular, with a particular choice of the test and the arbitrary output distribution we recover the exact error probability of the code in almost-lossless source coding, channel coding and almost-lossless joint source-channel coding. The formulation allows to recover previous converse results in the literature and identify the steps where tightness is lost. Extensions of the method to the lossy case are also reviewed.

| PDF Presentation
16:30 Break
16:45 Hiroshi Nagaoka (The University of Electro-Communications, Tokyo)
Classical and quantum simple hypothesis testing revisited
Arrow Abstract

We revisit to the asymptotics of simple hypothesis testing for classical and quantum states from several viewpoints to give some new observations, focusing upon the contrasts between information-spectrum settings and i.i.d.-theorems, Hoeffding-domain and strong converse-domain, the relative entropy and Renyi-type entropies, etc.

17:25 Robert König (IQC, University of Waterloo)
Dissipative encoding and state preparation for topological order
Arrow Abstract

We study the suitability of dissipative (non-unitary) processes for (a) encoding logical information into a topologically ordered ground space and (b) preparing an (arbitrary) topologically ordered state. We give a construction achieving (a) in time O(L) for the L×L-toric code by evolution under a geometrically local, time-independent Liouvillean. We show that this scaling is optimal: even the easier problem (b) takes at least Ω(L) time when allowing arbitrary (possibly time-dependent) dissipative evolution. For more general topological codes, we obtain similar lower bounds on the required time for (a) and (b). These bounds involve the code distance and the dimensionality of the lattice. The proof involves Lieb-Robinson bounds, recent cleaning-lemma-type arguments for topological codes, as well as uncertainty relations between complementary observables. By allowing general locality-preserving evolutions (including, e.g., circuits of CPTPMs), our work extends earlier work characterizing unitary state preparation.
This is joint work with John Dengis and Fernando Pastawski.

| PDF Presentation
18:00 End of the day

20 May, Tues Session Chairs: Stephanie Wehner (Morning), Valerio Scarani (Afternoon)
09:00 Andreas Winter (Universitat Autònoma de Barcelona)
Strong converses for quantum channel capacities
Arrow Abstract

Channel capacities are the maximum rate of information (quantum, classical, private, ...) at which many independent uses of a channel can perform asymptotically reliably. By contrapositive, at larger rates, the error parameter cannot go to zero. But what is the real tradeoff between error and amount of information transmitted by $n \gg 1$ channel uses? For many situations in the classical information theory, it turns out that a "strong converse" holds, which means that for rates above the capacity, the error goes to its maximum (usually unity). This is a non-trivial statement, and not necessarily true, for instance in models with memory. Even without memory, it is not an easy result; in the talk i will discuss the challenges in establishing strong converses for quantum channel capacities, and the techniques that have been used to obtain them, or partial results. A strong converse can be viewed as a first step towards a more detailed finite blocklength understanding of the channel performance: Once we know it, we learn that for any error $0 < \epsilon < 1$, the amount of information that can be sent is $nC + f(\epsilon)o(n)$, with some function $f(\epsilon)$ and a sub-linear function $o(n)$ of the number $n$ of channel uses. This is the starting point of the so-called second-order analysis: i.e., the characterization of the functions $f(\epsilon)$ and $o(n)$.

| PDF Presentation
10:00 Coffee/Tea Break
10:30 Ciara Morgan (Leibniz Universität Hanover)
Efficient achievability for quantum protocols using decoupling theorems
Arrow Abstract

Proving achievability of protocols in quantum Shannon theory usually does not consider the efficiency at which the goal of the protocol can be achieved. Nevertheless it is known that protocols such as coherent state merging are efficiently achievable at optimal rate. We aim to investigate this fact further in a general one-shot setting, by considering certain classes of decoupling theorems and give exact rates for these classes. Moreover we compare results of general decoupling theorems using Haar distributed unitaries with those using smaller sets of operators, in particular $\epsilon$-approximate 2-designs. We also observe the behavior of our rates in special cases such as $\epsilon$ approaching zero and the asymptotic limit.
This is joint work with Christoph Hirche.

| PDF Presentation
11:10 Masahito Hayashi (Nagoya University/CQT NUS)
Asymptotic conversion of probability distribution and entangled state
Arrow Abstract

The classical and quantum security can be treated as conversion of probability distribution with classical and quantum side information. Further, conversion of entangled state by LOCC is also reduced to conversion of probability distribution. Firstly, I present our results for generation of uniform distribution with classical and quantum side information the one-shot form. Then, I apply it to quantum independent and identical case and classical Markovian case with asymptotic analysis. Further, I extended this analysis to conversion between arbitrary independent and identical distributions without side information. I also consider the reversible conversion.
This talk contains joint works with Marco Tomamichel, Shun Watanabe, Toyohiro Tsurumaru, Wataru Kumagai, and Kosuke Ito.

| PDF Presentation
11:50 Shun Watanabe (University of Tokushima)
A Converse Bound on Secret Key Agreement and Its Applications
Arrow Abstract

We consider secret key agreement by multiple parties observing correlated data and communication interactively over an insecure communication channel. By relating secret key agreement and binary hypothesis testing, we derive a single-shot converse bound on the length of secret key. Furthermore, we apply the bound for secure computation problems, and derive converse bounds on those problems.
The talk is based on joint work with Himanshu Tyagi (https://eprint.iacr.org/2014/088).

| PDF Presentation
12:25 Lunch-break
13:45 Yaoyun Shi (University of Michigan, Ann Arbor)
Reining in quantum adversaries: the case of randomness expansion
Arrow Abstract

How can we generate near-perfect randomness securely, in large quantities, and efficiently? This is an important question for modern day information processing, especially for cryptography. Randomness expansion protocols provide a remarkable quantum solution based on Bell inequality violations. Such a protocol transforms a uniform seed to a much longer random output, by interacting classically with communication-restricted quantum devices whose inner-workings may be imperfect or even malicious. In this talk, I will analyze a variant of known protocols, showing that this class of exponentially expanding protocols not only are quantum-secure, but also enjoy several highly desirable new features such as cryptographic level of security, tolerance of a constant level of device imperfection, etc. Those features widen the application scope of the protocols and facilitate their practical implementations using current technologies. My talk will emphasize our proof techniques for managing two sources of security challenges: the repeatedly used devices that may cheat adaptively, and the adversary who may exploit her quantum correlation with the devices to reduce the output randomness. A notion of quantum Renyi entropy recently shown by several authors to be useful for quantum information theory also plays an instrumental role in our proof.
Joint work with Carl A. Miller (arXiv:1402.0489).

| PDF Presentation
14:45 Coffee/Tea Break
15:15 Yanbao Zhang (IQC, University of Waterloo)
Analysis of tests of local realism
Arrow Abstract

Reliable rejection of local realism is highly desirable not only for understanding the foundation of quantum mechanics but also for facilitating quantum information tasks, such as quantum key distribution and randomness generation. The confidence for rejecting local realism is usually estimated by comparing Bell-inequality violation with experimental standard deviation. However, as we show, this method can overestimate the rejection confidence and so is not valid. We propose a prediction-based ratio (PBR) protocol to lower bound the rejection confidence without using a predetermined Bell inequality. The PBR protocol works even if the prepared quantum state, measurement settings, and local realistic models vary arbitrarily during an experiment. If the prepared state and measurement settings do not vary, the rejection-confidence bound is asymptotically tight. For comparison, confidence bounds derived from Bell-inequality violations using martingale theory [R. Gill, arXiv:quant-ph/0110137] are studied. It is found that bounds from martingale theory are not tight. We also simplify the implementation of the PBR protocol by using a set of predetermined Bell inequalities. The simplified PBR protocol can be applied to any test with linear witnesses, such as tests for verifying entanglement, contextuality, or system dimensionality.

| PDF Presentation
15:55 Graeme Smith (IBM, New York)
Bound entangled states with secret key and their classical counterpart
Arrow Abstract

Entanglement is a fundamental resource for quantum information processing. In its pure form, it allows quantum teleportation and sharing classical secrets. Realistic quantum states are noisy and their usefulness is only partially understood. Bound-entangled states are central to this question---they have no distillable entanglement, yet sometimes still have a private classical key. We present a construction of bound-entangled states with private key based on classical probability distributions. From this emerge states possessing a new classical analogue of bound entanglement, distinct from the long-sought bound information. We also find states of smaller dimensions and higher key rates than previously known. Our construction has implications for classical cryptography: we show that existing protocols are insufficient for extracting private key from our distributions due to their "bound-entangled" nature. We propose a simple extension of existing protocols that can extract key from them.

16:30 Break
16:45 Nilanjana Datta (University of Cambridge)
Second-order asymptotics for source coding, dense coding and pure-state entanglement conversions
Arrow Abstract

We introduce two variants of the information spectrum relative entropy defined by Tomamichel and Hayashi which have the particular advantage of satisfying the data- processing inequality. This property allows us to obtain one-shot bounds for various information-processing tasks in terms of these quantities. In contrast to one-shot bounds given in terms of smooth min-/max- entropies, these bounds can be numerically computed to arbitrary precision. Moreover, these relative entropies have a second order asymptotic expansion, which in turn yields tight second order asymptotics for optimal rates of these tasks in the i.i.d. setting. The tasks considered are fixed-length quantum source coding, noisy dense coding, entanglement concentration and pure-state entanglement dilution. We also prove how the discrepancy between the optimal rates of entanglement concentration and dilution in the second order implies the irreversibility of entanglement concentration established by Kumagai and Hayashi. In addition, the spectral divergence rates of the Information Spectrum Approach (ISA) can be retrieved from our relative entropies in the asymptotic limit. This enables us to directly obtain the more general results of the ISA from our one-shot bounds.
This is joint work with Felix Leditzky.

| PDF Presentation
17:25 Yuval Kochman (Hebrew University of Jerusalem)
Rate-distortion theory: did we get it all wrong?
Arrow Abstract

In this talk we revisit some basic definitions in rate-distortion theory, and argue that they fail to capture the full operational trade-offs of compression. Specifically, we argue that the concept of expected distortion, which strikes a balance between the reconstruction quality given different source values is not suitable in many scenarios. We also consider the excess-distortion probability, and find that it unnecessarily couples the quantizer dimension with user experience. For both issues, we offer some remedy in the form of new information-theoretic quantities.
Based on joint work with Uri Erez and Gregory W. Wornell.

| PDF Presentation
19:30 Conference Dinner

21 May, Wed Session Chairs: Mario Berta (Morning), Masahito Hayashi(Afternoon)
09:00 Renato Renner (ETH Zürich)
Axiomatic approach towards single-shot entropies
Arrow Abstract

One possibility to motivate single-shot entropies, in particular (smooth) min- and max-entropy, is their relation to operational quantities, such as coding length (in the classical case) or state merging (in the quantum case). In this talk, I will describe a different, more axiomatic approach, which is inspired by recent work in thermodynamics by Lieb and Yngvason. The idea is to consider an order relation that defines a set of possible state transformations. Provided this order relation satisfies certain requirements, it induces entropy functions which turn out to correspond to the usual min- and max-entropy.

| Presentation Notes
10:00 Coffee/Tea Break
10:30 Frédéric Dupuis (Aarhus University)
On quantum Rényi entropies: a new definition and some properties
Arrow Abstract

The Rényi entropies constitute a family of information measures that generalizes the well-known Shannon entropy, inheriting many of its properties. They appear in the form of unconditional and conditional entropies, relative entropies or mutual information, and have found many applications in information theory and beyond. Various generalizations of Rényi entropies to the quantum setting have been proposed, most prominently Petz's quasi-entropies and Renner's conditional min-, max- and collision entropy. However, these quantum extensions are incompatible and thus unsatisfactory.

We propose a new quantum generalization of the family of Rényi entropies that contains the von Neumann entropy, min-entropy, collision entropy and the max-entropy as special cases, thus encompassing most quantum entropies in use today. We show several natural properties for this definition, including data-processing inequalities, a duality relation, and an entropic uncertainty relation.

| PDF Presentation
11:10 Milán Mosonyi (Universitat Autònoma de Barcelona)
Operational interpretations of Renyi divergences
Arrow Abstract

We show that the new quantum extension of Renyi's alpha-divergences, introduced recently by Muller-Lennert, Dupuis, Szehr, Fehr and Tomamichel, J. Math. Phys. 54, 122203 (2013) , and Wilde, Winter, Yang, arXiv:1306.1586, have an operational interpretation in the strong converse problem of quantum hypothesis testing. Together with related results for the direct part of quantum hypothesis testing, known as the quantum Hoeffding bound, our result suggests that the operationally relevant definition of the quantum Renyi divergences depends on the parameter alpha: for alpha<1, the right choice seems to be the traditional definition, whereas for alpha>1, the right choice is the newly introduced version. Our results hold not only in the usual i.i.d. scenario, but also for various correlated states on a spin chain. (Joint work with Tomohiro Ogawa)

| PDF Presentation
11:50 Koenraad Audeneart (Royal Holloway University of London)
Relative Rényi entropies, from α to z
Arrow Abstract

We consider a two-parameter family of relative Rényi entropies that unifies the study of several known relative entropies (or divergences). These include the quantum relative entropy, the recently defined quantum Rényi divergences, as well as the original quantum relative Rényi entropies. Consequently, the data-processing inequality for all these quantities follows directly from the data-processing inequality for these new relative entropies, the proof of which is one of the main technical contributions of this work. These new relative Rényi entropies stem from the quantum entropic functionals defined by Jak\v{s}i\'c {\em{et al.}} in the context of non-equilibrium statistical mechanics, and they satisfy the quantum generalizations of Rényi's axioms for a divergence. We investigate a variety of limiting cases for the two parameters, obtaining explicit formulas for each one of them.

| PDF Presentation
12:25 Lunch-break
13:45 Te Sun Han (NICT, Japan)
On 1st and 2nd-order ε-capacity theorems for discrete memoryless channels with general mixture
Arrow Abstract

Our main interest in this talk is in variousε-capacity problems, not only because it is in nice accordance with the information spectrum methods, but also because it is of great importance from the viewpoint of 2nd order capacity in the finite block length regime. Here, we focus on the case of discrete memoryless channels with general mixture, where two direct lemmas and two converse lemmas play the key role.

| PDF Presentation
14:45 Coffee/Tea Break
15:15 Yury Polyanskiy (MIT, Cambridge, MA )
Dissipation of Information in Channels with Input Constraints
Arrow Abstract

One of the basic tenets in information theory, the data processing inequality, states that output divergence does not exceed the input divergence for any channel. For channels without input constraints, various estimates on the amount of such contraction are known, e.g., Dobrushin's coefficient for the total variation. This work investigates channels with average input cost constraint. It is found that while the contraction coefficient typically equals one, the information nevertheless dissipates. A certain non-linear function, a Dobrushin curve of the channel, is proposed to quantify the amount of dissipation. Tools for evaluating the Dobrushin curve of additive-noise channels are developed. Applications in stochastic control, uniqueness of Gibbs measures and noisy circuits are discussed. Based on a joint work with Y. Wu (UIUC).

| PDF Presentation
15:55 Min-Hsiu Hsieh (University of Technology Sydney)
The Private and Public Correlation Costs of Three Random Variables with Collaboration
Arrow Abstract

In this talk we consider the problem of generating arbitrary three-party correlations from a combination of public and secret correlations. Two parties - called Alice and Bob - share perfectly correlated bits that are secret from a collaborating third party, Charlie. At the same time, all three parties have access to a separate source of correlated bits, and their goal is to convert these two resources into multiple copies of some given tripartite distribution PXY Z. We obtain a single-letter characterization of the trade-off between public and private bits that are needed to achieve this task. The rate of private bits is shown to generalize Wyner’s classic notion of common information held between two two random variables. The problem we consider is also closely related to the task of secrecy formation in which PXY Z is generated using public communication and local randomness, however Charlie now functions as an adversary instead of a collaborator. We describe in detail the differences between the collaborative and adversarial scenarios.

| PDF Presentation
16:30 Break
16:45 Fernando G.S.L. Brandão (University College London)
Quantum de Finetti Theorems
Arrow Abstract

A very useful tool for connection non i.i.d. problems to i.i.d. ones are the so-called quantum de Finetti theorems. In this talk I will review some recent advances in the study of quantum de Finetti theorems and pose open problems for future research.

| Blackboard talk
17:25 End of the day


   
Centre for quantum technologies National University of Singapore