# Seminars (MQI)

Videos and presentation materials from other INI events are also available.

Search seminar archive

Event When Speaker Title Presentation Material
MQI 28th August 2013
14:00 to 16:00
R Koenig Quantum entropy power inequalities
MQI 29th August 2013
14:00 to 15:00
G Gour Towards a complete classification of multipartite entanglement
MQIW01 2nd September 2013
10:00 to 11:00
T Vidick Lecture 1: Entanglement in quantum interactive proofs (tutorial)
In the first lecture I will present the reasonably well-understood topic of entanglement in XOR games. We will review results by Tsirelson and Slofstra which provide lower and upper bounds on the dimension of entanglement required to play (near-)optimally. These results are obtained through connections with semidefinite programming and the theory of C*-algebras.

In the second lecture I will move to more general classes of games. I will introduce an interesting "universal" class of entangled states, embezzlement states, and discuss some of their properties. I will present some lower bounds on entanglement dimension, leaving the proof of upper bounds as an exercise to the audience. Time permitting I will connect these results to the complexity theory of multi-prover interactive proofs.

MQIW01 2nd September 2013
11:30 to 12:30
Classical and quantum de Finetti theorems
This will be a basic tutorial on the classical and quantum de Finetti theorems, focussing on the finite versions of the theorem.
MQIW01 2nd September 2013
14:00 to 15:00
Lecture 1: Information-Theoretic Techniques in Many-Body Physics
MQIW01 2nd September 2013
15:30 to 16:30
A Harrow Separable states, the unique games conjecture and monogamy of entanglement
Co-authors: Boaz Barak (MSR), Fernando Brandao (UCL), Jon Kelner (MIT), Ashley Montanaro (Bristol), David Steurer (Cornell), Yuan Zhou (CMU)

The quantum separability problem---determining when a density matrix is entangled or when it is separable---is an old problem in quantum information theory. Although solving this problem to accuracy inverse-polynomial in dimension is NP-hard, only loose bounds are known on the complexity of the constant-error case. In this talk, I will describe some surprising connections between the quantum separability problem and a major open problem in classical computer science known as the unique games conjecture. Remarkably, even the proposed solutions to both problems turn out to be essentially the same, so that bounds on the monogamy of entanglement (aka de Finetti theorems) can be used to analyze the performance of classical algorithms. I will also describe conjectured monogamy bounds that are an alternate route to resolving the unique games conjecture.

Based on 1001.0017, 1205.4484 and 1210.6367.

Related Links •http://arxiv.org/abs/1001.0017 - Testing product states, quantum Merlin-Arthur games and tensor optimisation •http://arxiv.org/abs/1205.4484 - Hypercontractivity, Sum-of-Squares Proofs, and their Applications •http://arxiv.org/abs/1210.6367 - Quantum de Finetti Theorems under Local Measurements with Applications

MQIW01 2nd September 2013
16:30 to 17:30
TS Cubitt Undecidability of the spectral gap problem
Co-authors: David Perez-Garcia (Universidad Complutense de Madrid), Michael Wolf (Technische Universität München)

The spectral gap of a quantum many-body Hamiltonian plays a crucial role in determining its physical properties. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring where the spectral gap vanishes.

A number of longstanding open problems in mathematical physics, such as the Haldane conjecture or the 2D AKLT gap conjecture, concern spectral gaps of particular many-body models. In the related setting of quantum field theories, determining if Yang-Mills theory is gapped is one of the Millennium Prize Problems. Numerous important results about many-body Hamiltonians only apply to gapped systems. Determining when a model is gapped or gapless is therefore one of the primary goals of theoretical condensed matter physics.

I will show that the spectral gap problem is unsolvable in general. Specifically, we prove that there exist translationally-invariant Hamiltonians on a 2D square lattice of finite-dimensional spins, with two-body nearest-neighbour interactions, for which the spectral gap problem is undecidable. This means that there exist Hamiltonians for which the presence or absence of a spectral gap cannot be proven in any consistent framework of mathematics.

The proof is (of course!) by reduction from the Halting Problem. But the construction is complex, and draws on a wide variety of techniques: from quantum algorithms and quantum computing, to classical tiling problems, to recent Hamiltonian complexity results, to even more recent PEPS constructions. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for physics (which after all happens in the laboratory, not in Hilbert space!).

MQIW01 3rd September 2013
09:00 to 10:00
T Vidick Lecture 2: Entanglement in quantum interactive proofs (tutorial)
In the first lecture I will present the reasonably well-understood topic of entanglement in XOR games. We will review results by Tsirelson and Slofstra which provide lower and upper bounds on the dimension of entanglement required to play (near-)optimally. These results are obtained through connections with semidefinite programming and the theory of C*-algebras.

In the second lecture I will move to more general classes of games. I will introduce an interesting "universal" class of entangled states, embezzlement states, and discuss some of their properties. I will present some lower bounds on entanglement dimension, leaving the proof of upper bounds as an exercise to the audience. Time permitting I will connect these results to the complexity theory of multi-prover interactive proofs.

MQIW01 3rd September 2013
10:00 to 11:00
Lecture 2: Information-Theoretic Techniques in Many-Body Physics
MQIW01 3rd September 2013
11:30 to 12:30
Lecture 1: Operator Space theory: a natural framework for Bell inequalities
Lecture 1: In the first lecture, I will introduce the mathematical theory of Operator Spaces and sketch why it enters so naturally in the study of nonlocal games.

Lecture 2: In the second lecture, I will review some of the results one can obtain with that machinery to illustrate its power. I will finish with some open questions and future directions for research.

MQIW01 3rd September 2013
14:00 to 15:00
Lecture 1: Random matrix theory with a view towards free probability, and connections to quantum information
I will discuss results in random matrix theory that have found applications in quantum information. The approach will be mainly combinatorial and this will be the occasion to introduce the audience to free probability theory. The main points will be illustrated with examples coming from quantum information: random density matrices, thresholds for entanglement criteria, minimum output entropies for random quantum channels.
MQIW01 3rd September 2013
15:30 to 16:30
The little we know about LOCC
Co-authors: Andrew Childs (University of Waterloo), Eric Chitambar (Southern Illinois University), Laura Mancinska (University of Waterloo), Maris Ozols (University of Waterloo), Andreas Winter (ICREA and Autonomus University of Barcelona)

Consider the subset of multipartite quantum operations that can be implemented when the parties are restricted to using local quantum operations and classical communication (LOCC). We summarize recent results concerning LOCC -- in particular, what extra information processing tasks can be implemented (or not) if unlimited rounds of communication and vanishing error is allowed. We discuss extensions to the nonlocality without entanglement phenomenon.

Joint works with Andrew Childs, Eric Chitambar, Laura Mancinska, Maris Ozols, Andreas Winter (plus additional results due to Matthias Kleinmann, Hermann Kampermann, Dagmar Bruss, Wei Cui, Hoi-Kwong Lo, Runyao Duan, and Min-Hsiu Hsieh)

MQIW01 4th September 2013
09:00 to 10:00
Lecture 2: Operator Space theory: a natural framework for Bell inequalities
Lecture 1: In the first lecture, I will introduce the mathematical theory of Operator Spaces and sketch why it enters so naturally in the study of nonlocal games.

Lecture 2: In the second lecture, I will review some of the results one can obtain with that machinery to illustrate its power. I will finish with some open questions and future directions for research.

MQIW01 4th September 2013
10:00 to 11:00
Lecture 2: Random matrix theory with a view towards free probability, and connections to quantum information
I will discuss results in random matrix theory that have found applications in quantum information. The approach will be mainly combinatorial and this will be the occasion to introduce the audience to free probability theory. The main points will be illustrated with examples coming from quantum information: random density matrices, thresholds for entanglement criteria, minimum output entropies for random quantum channels.
MQIW01 4th September 2013
11:30 to 12:30
Lecture 1: A Primer in Random Matrix Theory
I will review some basic ideas and results in random matrix theory.
MQIW01 4th September 2013
14:00 to 15:00
Lecture 1: One-shot Quantum Information Theory I: Entropic Quantities
Optimal rates of quantum information-processing tasks, such as compression and transmission of information, and manipulation of entanglement, were initially obtained in the so-called "asymptotic, memoryless setting". In this setting, the underlying resources (e.g. information sources, channels and entanglement resources) are assumed to be memoryless, and to be available for asymptotically many uses. The optimal rates were shown to be given in terms of entropic quantities expressible in terms of the quantum relative entropy.

In real-world communications and cryptographic systems, this setting is not generally valid: resources are used a finite number of times, and there may be correlations between their successive uses. Hence, it is important to evaluate the fundamental limits on information-processing tasks in the "one-shot setting", in which one considers a finite number of uses of arbitrary resources.

In the first lecture, I will discuss entropic quantities which play an important role in the one-shot setting, highlighting their salient mathematical properties and operational significances.

In the second lecture, I will focus on the problem of transmission of information through quantum channels, to illustrate how some of the entropic quantities (introduced in the first lecture) arise naturally in the one-shot setting.

MQIW01 4th September 2013
15:30 to 16:30
Free compression norms and Lp norms
Co-authors: Serban Belinschi (Queen's), Ion Nechita (CNRS, Toulouse UPS)

I will talk about a new norm that shows up naturally in the framework of random quantum channels. This norm relies on free probability theory and is called the free compression norm. We show that the problem of comparing it to Lp norms has applications to the understanding of the minimum output entropy (MOE) of typical quantum random channels. As an application, we establish violation of additivity of the MOE for typical quantum channels with Bell states, and find in this framework the optimal output dimension and the optimal violation.
MQIW01 4th September 2013
16:30 to 17:30
On spectral convergence bounds and the undecidability of control problems
MQIW01 5th September 2013
09:00 to 10:00
Lecture 2: A Primer in Random Matrix Theory
I will review some basic ideas and results in random matrix theory.
MQIW01 5th September 2013
10:00 to 11:00
Lecture 2: One-shot Quantum Information Theory II: Information Transmission
Optimal rates of quantum information-processing tasks, such as compression and transmission of information, and manipulation of entanglement, were initially obtained in the so-called "asymptotic, memoryless setting". In this setting, the underlying resources (e.g. information sources, channels and entanglement resources) are assumed to be memoryless, and to be available for asymptotically many uses. The optimal rates were shown to be given in terms of entropic quantities expressible in terms of the quantum relative entropy.

In real-world communications and cryptographic systems, this setting is not generally valid: resources are used a finite number of times, and there may be correlations between their successive uses. Hence, it is important to evaluate the fundamental limits on information-processing tasks in the "one-shot setting", in which one considers a finite number of uses of arbitrary resources.

In the first lecture, I will discuss entropic quantities which play an important role in the one-shot setting, highlighting their salient mathematical properties and operational significances.

In the second lecture, I will focus on the problem of transmission of information through quantum channels, to illustrate how some of the entropic quantities (introduced in the first lecture) arise naturally in the one-shot setting.

MQIW01 5th September 2013
11:30 to 12:30
A new definition for the quantum conditional Rényi entropy
Very recently, a new definition for the quantum conditional Rényi entropy has been proposed. Unlike previous definitions, it satisfies most of the basic properties one would expect from a conditional entropy, and it coincides with other widely used entropies (min-, max- and collision entropy) for appropriate choices of parameters. It has also found an application to prove a strong converse for coding over entanglement breaking channels. I will present these recent developments and try to show why this might be the "right" definition.
MQIW01 5th September 2013
14:00 to 15:00
Lecture 1: Concentration of measure (tutorial)
I will present an overview of the concentration of measure phenomenon, results and techniques, starting with Levy's isoperimetric inequality on the Euclidean sphere and following up with examples in other settings: Gaussian, discrete etc. I will also sketch some applications such as Dvoretzky's theorem on almost spherical sections of convex bodies and indicate some links to quantum information.
MQIW01 5th September 2013
15:30 to 16:30
Lecture 1 - Quantum walk and learning graph based algorithms (a tutorial)
In this talk I survey two generic methods to design quantum algorithms. I give an intuitive treatment of the discrete time quantization of classical Markov chains, and I describe nested walks, an extension of the model using quantum data structures. I explain the relatively recent idea of learning graphs, a combinatorial way to conceive quantum query algorithms. With several examples, including triangle and 3-collision finding, I illustrate the power of these methods. Finally I discuss time efficient implementations of learning graphs by quantum walks.
MQIW01 5th September 2013
16:30 to 17:30
Lecture 1: Introduction to Quantum Complexity (tutorial)
Coauthors: David Gosset, Sandeep Narayanaswami and Sean Hallgren

In this and tomorrow's lecture, we will look at why frustrated (local Hamiltonian) and unfrustrated (quantum SAT) problems can be very hard to solve, even for the computers we don't have yet. The keywords are: universal computation, ground states, locality, qudits, promise gaps, eigenvalue gaps, history states, clocks, and translational invariance.

The goal is to build the basics so that we can focus on recent ideas about the Quantum 3-SAT problem, random Quantum SAT (its SAT/UNSAT transition), perfect verifiers (QMA_1 vs QMA), quantum walks (the difficulty of solving scattering), blind quantum computation (limited power of QMA verifiers) and QMA vs. QCMA (MQA).

MQIW01 6th September 2013
09:00 to 10:00
Lecture 2: Concentration of measure (tutorial)
I will present an overview of the concentration of measure phenomenon, results and techniques, starting with Levy's isoperimetric inequality on the Euclidean sphere and following up with examples in other settings: Gaussian, discrete etc. I will also sketch some applications such as Dvoretzky's theorem on almost spherical sections of convex bodies and indicate some links to quantum information.
MQIW01 6th September 2013
10:00 to 11:00
Lecture 2 - Quantum walk and learning graph based algorithms (a tutorial)
In this talk I survey two generic methods to design quantum algorithms. I give an intuitive treatment of the discrete time quantization of classical Markov chains, and I describe nested walks, an extension of the model using quantum data structures. I explain the relatively recent idea of learning graphs, a combinatorial way to conceive quantum query algorithms. With several examples, including triangle and 3-collision finding, I illustrate the power of these methods. Finally I discuss time efficient implementations of learning graphs by quantum walks.
MQIW01 6th September 2013
11:30 to 12:30
Lecture 2: Introduction to Quantum Complexity (tutorial)
Coauthors: David Gosset, Sandeep Narayanaswami and Sean Hallgren

In this and tomorrow's lecture, we will look at why frustrated (local Hamiltonian) and unfrustrated (quantum SAT) problems can be very hard to solve, even for the computers we don't have yet. The keywords are: universal computation, ground states, locality, qudits, promise gaps, eigenvalue gaps, history states, clocks, and translational invariance.

The goal is to build the basics so that we can focus on recent ideas about the Quantum 3-SAT problem, random Quantum SAT (its SAT/UNSAT transition), perfect verifiers (QMA_1 vs QMA), quantum walks (the difficulty of solving scattering), blind quantum computation (limited power of QMA verifiers) and QMA vs. QCMA (MQA).

MQIW01 6th September 2013
14:00 to 14:30
Boson-Sampling in the light of sample complexity
Boson-Sampling is a classically computationally hard problem that can - in principle - be efficiently solved with linear quantum optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach.
MQIW01 6th September 2013
14:30 to 15:00
Entanglement recycling and generalized teleportation
Co-authors: Jonathan Oppenheim (UCL), Michal Horodecki (U of Gdansk)

I will introduce new teleportation protocols which are generalizations of the original teleportation protocols that use the Pauli group and the port-based teleportation protocols, introduced by Hiroshima and Ishizaka, that use the symmetric permutation group. I will show sufficient conditions for a set of operations, to give rise to a teleportation protocol and provide examples of such schemes. This generalization leads to protocols with novel properties and is needed to push forward new schemes of computation based on them. Port-based teleportation protocols and our generalizations use a large resource state consisting of N singlets to teleport only a single qubit state reliably. We provide two distinct protocols which recycle the resource state to teleport multiple states with error linearly increasing with their number. The first protocol consists of sequentially teleporting qubit states, and the second teleports them in a bulk.

MQIW01 6th September 2013
15:30 to 16:30
A Ambainis Exact quantum algorithms
A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1) - in contrast to the usual model in which a quantum algorithm is allowed to output an incorrect answer with a small probabilities. Coming up with exact quantum algorithms is a difficult task because we have to ensure that no amplitude ends up in a state corresponding to an incorrect answer - on any input.

We present the first example of a Boolean function f(x1, ..., xN) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^{0.8675...}) queries.

MQIW01 6th September 2013
16:30 to 17:30
Quantum Information for Optical Microscopy
Co-authors: Richard Küng (University of Freiburg), Felix Krahmer (University of Goettingen)

Optical sensors pick up the intensity of light fields, but are insensitive to phase. It is, however, conceivable that an "overcomplete" set of intensity measurements may allow one to reconstruct the complete state of the light field emanating from a given object. In the past two years, stable algorithms with rigorous performance guarantees for this "phase recovery problem" have been developed. They are ultimately based on low-rank matrix recovery algorithms whose technical analysis has benefited from methods originating in quantum information. I will review these developments and present new results towards the de-randomization of phase estimation protocols.

MQI 11th September 2013
15:00 to 16:00
The resource theory of magic states
MQI 12th September 2013
13:30 to 14:30
Random thoughts
MQI 17th September 2013
14:00 to 15:00
When do local operations and classical communication suffice for two-qubit state discrimination?
MQI 19th September 2013
14:00 to 15:00
A Cabello A graph-theoretic approach to quantum correlations and the exclusivity principle
MQI 24th September 2013
14:00 to 15:00
G Pisier Quantum expanders and growth of operator spaces
MQI 26th September 2013
13:30 to 14:30
On equivalence between Popescu-Rohrlich boxes and random access codes
We study a problem of interconvertibility of two supra-quantum resources: one is so called PR-box, which violates CHSH inequality up to maximal algebraic bound, and second is so called random access code (RAC). The latter is a functionality that enables Bob (receiver) to choose one of two bits of Alice. It has been known, that PR-box supplemented with one bit of communication can be used to simulate RAC. We ask the converse question: to what extent RAC can simulate PR-box? To this end we introduce "racbox": a box such that supplemented with one bit of communication offers RAC. As said, PR-box can simulate racbox. The question we raise, is whether any racbox can simulate PR-box. We show that a non-signaling racbox indeed can simulate PR-box, hence those two resources are equivalent. We also provide an example of signalling racbox which cannot simulate PR-box. We give a resource inequality between racboxes and PR-boxes, and show that it is saturated.
MQI 1st October 2013
14:00 to 15:00
What is the origin of complex probability amplitudes?
I begin this presentation with an attempt to explain the origin of probability amplitudes in quantum theory, but the explanation makes sense only if those amplitudes are real. This result provides motivation for studying the real-vector-space variant of quantum theory. I show how a particular model within real-vector-space quantum theory can produce the appearance of complex probability amplitudes. In this model, a special binary subsystem of the universe, called the universal rebit or “ubit,” plays the role of the complex phase factor. In a certain limit the effective theory emerging from the model mimics standard quantum theory, but if we stop short of this limit the model predicts the spontaneous decoherence of isolated systems.
MQI 2nd October 2013
14:00 to 15:00
M Rangamani Holographic tutorial
A tutorial and discussion on Holography, geared towards a quantum information audience.
MQI 3rd October 2013
14:00 to 15:00
Zero-Error Classical Channel Capacity and Simulation Cost Assisted by Quantum Non-Signalling Correlations
We study the one-shot zero-error classical capacity of quantum channels assisted by quantum non-signalling correlations, and the reverse problem of exact simulation. Both lead to simple semi-definite programmings whose solutions can be given in terms of the conditional min-entropies. We show that the asymptotic simulation cost is precisely the conditional min-entropy of the Choi-Jamiolkowski matrix of the given channel. For classical-quantum channels, the asymptotic capacity is reduced to a quantum fractional packing number suggested by Harrow, which leads to an operational interpretation of the celebrated Lovasz function as the zero-error classical capacity of a graph assisted by quantum non-signalling correlations. This talk is based on a joint work with Andreas Winter (UAB).
MQI 8th October 2013
14:00 to 15:00
Quantum skew divergence
MQI 10th October 2013
14:00 to 15:00
Thermodynamics of discrete quantum processes
MQIW02 14th October 2013
10:00 to 11:00
M Christandl & M Walter Welcome and Overview Talk by the Organisers
MQIW02 14th October 2013
11:30 to 12:30
The classical entropy of quantum states
Co-author: Elliott Lieb (Princeton University)

To quantify the inherent uncertainty of quantum states Wehrl ('79) suggested a definition of their classical entropy based on the coherent state transform. He conjectured that this classical entropy is minimized by states that also minimize the Heisenberg uncertainty inequality, i.e., Gaussian coherent states. Lieb ('78) proved this conjecture and conjectured that the same holds when Euclidean Glauber coherent states are replaced by SU(2) Bloch coherent states. This generalized Wehrl conjecture has been open for almost 35 years until it was settled last year in joint work with Elliott Lieb. Recently we simplified the proof and generalized it to SU(N) for general N. I will present this here.

MQIW02 14th October 2013
14:00 to 15:00
K Mulmuley The complexity of Kronecker Coefficients
The Kronecker coefficients are of fundamental importance in representation theory and quantum physics. Their complexity turns out to be of fundamental importance in the Geometric Complexity Theory (GCT) program towards that P vs. NP and related problems. In this talk we will describe some results related to the complexity of Kronecker coefficients.
MQIW02 14th October 2013
15:30 to 16:30
Quantum marginals: the generic entanglement regime
Co-authors: Stanislaw SZAREK (Universite Paris 6 & Case Western Reserve University), Deping YE (Memorial University of Newfoundland)

Consider N qubits in a generic pure state on $(C^2)^{\otimes N}$. Give a fraction $p \in (0,1/2)$ of them to Alice, another fraction $p$ of them to Bob, and assume the remaining qubits disappear in the environment. Do Alice and Bob share some entanglement ?

When N is large, this problem features a threshold phenomenon around the critical value $p=1/5$. In this talk I give an elementary proof of the "easy" half of this result: for $p>1/5$, entanglement is generic. The general question, and a discussion of the threshold phenomenon, will be addressed in the talk by S. Szarek.

I will introduce background from high-dimensional convex geometry and prove some key estimates on the size (specifically the mean width) of the set of separable states.

The talk is a variation on arxiv:1106.2264 (joint with S. Szarek and D. Ye).

MQIW02 14th October 2013
17:00 to 18:00
Quantum Shannon Theory: Rothschild Distinguished Visiting Fellow Lecture
The notions of channel and capacity are central to the classical Shannon theory. "Quantum Shannon theory" denotes a subfield of quantum information science which uses operator analysis, convexity and matrix inequalities, asymptotic techniques such as large deviations and measure concentration to study mathematical models of communication channels and their information-processing performance. From the mathematical point of view quantum channels are normalized completely positive maps of operator algebras, the analog of Markov maps in the noncommutative probability theory, while the capacities are related to certain norm-like quantities. In applications noisy quantum channels arise from irreversible evolutions of open quantum systems interacting with environment-a physical counterpart of a mathematical dilation theorem. It turns out that in the quantum case the notion of channel capacity splits into the whole spectrum of numerical information-processing characteristics depending on the kind of data transmitted (classical or quantum) as well as on the additional communication resources. An outstanding role here is played by quantum correlations - entanglement - inherent in tensor-product structure of composite quantum systems. This talk presents a survey of basic coding theorems providing analytical expressions for the capacities of quantum channels in terms of entropic quantities. We also touch upon some open mathematical problems, such as additivity and Gaussian optimizers, concerning the entropic characteristics of both theoretically and practically important Bosonic Gaussian channels.
MQIW02 15th October 2013
09:00 to 10:00
Marginal Entropies for Causal Inference and Quantum Non-Locality
Co-authors: Rafael Chaves (University of Freiburg), Lukas Luft (University of Freiburg)

The fields of quantum non-locality in physics, and causal discovery in machine learning, both face the problem of deciding whether observed data is compatible with a presumed causal relationship between the variables (for example a local hidden variable model). Traditionally, Bell inequalities have been used to describe the restrictions imposed by causal structures on marginal distributions. However, some structures give rise to non-convex constraints on the accessible data, and it has recently been noted that linear inequalities on the observable entropies capture these situations more naturally. In this talk, I will introduce the machine learning background, advertise the program of investigating entropic marginals, and present some recent results.

MQIW02 15th October 2013
10:00 to 11:00
A Harrow Group representations and quantum information theory
The method of types---classifying strings according to letter frequencies---is a fundamental tool of classical information theory. I will discuss a natural quantum generalisation, known as the Schur basis, in which quantum states are decomposed into irreps of the unitary and symmetric groups. First, I'll explain the analogy to the classical method of types and will review past work that applies the Schur basis to quantum information theory. Then I'll discuss applications to spectrum estimation, channel coding problems and mention some open problems.
MQIW02 15th October 2013
11:30 to 12:30
Eigencones and Levi movability
Let $g_{\lambda\mu\nu}$ denote the Kronecker coefficient. It is a multiplicity in the decomposition of the tensor product of two irreducible representations of the symmeric group. The set of triples $(\lambda,\mu,\nu)$ of bounded length such that $g_{\lambda\mu\nu}$ is nonzero generate a closed convex polyhedral cone. In this talk, we will give a description of these cones and more generaly of branching cones.

Some branching cones have an interpretation in terms of eigenvalues of Hermitian matrices known as the addive Horn problem. We will also give an answer of the so called multiplicative Horn problem.

MQIW02 15th October 2013
14:00 to 15:00
Operator norm convergence for sequence of matrices and application to QIT
Random matrix theory is the study of probabilistic quantities associated to random matrix models, in the large dimension limit. The eigenvalues counting measure and the eigenvalues spacing are amongst the most studied and best understood quantities. The purpose of this talk is to focus on a quantity that was less understood until recently, namely the operator norm of random matrices. I will state recent results in this direction, and mention three applications to quantum information theory: -a- convergence of the collection of images of pure states under typical quantum channels (joint with Fukuda and Nechita) -b- thresholds for random states to have the absolute PPT property (joint with Nechita and Ye), -c- new examples of k-positive maps (ongoing, joint with Hayden and Nechita).
MQIW02 15th October 2013
15:30 to 16:30
Threshold phenomena for quantum marginals
Co-authors: Guillaume Aubrun (U. Lyon 1), Deping Ye (Memorial U. of Newfoundland)

Consider a quantum system consisting of N identical particles and assume that it is in a random pure state (i.e., uniformly distributed over the sphere of the corresponding Hilbert space). Next, let A and B be two subsystems consisting of k particles each. Are A and B likely to share entanglement? Is the AB-marginal typically PPT?

As it turns out, for many natural properties there is a sharp "phase transition" at some threshold depending on the property in question. For example, there is a threshold K asymptotically equivalent to N/5 such that - if k > K then A and B typically share entanglement - if k The first statement was (essentially) shown in the talk by G. Aubrun. Here we present a general scheme for handling such questions and sketch the analysis specific to entanglement.

The talk is based on arxiv:1106.2264v3; a less-technical overview is in arxiv:1112.4582v2.
MQIW02 16th October 2013
09:00 to 10:00
Quantum correlations in Newtonian space and time: faster than light communication or nonlocality
Using a theorem that allows one to assert the presence of nonlocal correlations between parties that are never measured in the same run of an experiment (using marginal), we study the following question: Experimental violations of Bell inequalities using space-like separated measurements precludes the explanation of quantum correlations through causal influences propagating at subluminal speed. Yet, “everything looks as if the two parties somehow communicate behind the scene”. We investigate the assumption that they do so at a speed faster than light, though finite. Such an assumption doesn’t respect the spirit of Einstein relativity. However, it is not crystal clear that such “communication behind the scene” would contradict relativity. Indeed, one could imagine that this communication remains for ever hidden to humans, i.e. that it could not be controlled by humans, only Nature exploits it to produce correlations that can’t be explained by usual common causes. To define faster than light hidden communication requires a universal privileged reference frame in which this faster than light speed is defined. Again, such a universal privilege d frame is not in the spirit of relativity, but it is also clearly not in contradiction: for example the reference frame in which the cosmic microwave background radiation is isotropic defines such a privileged frame. Hence, a priori, a hidden communication explanation is not more surprising than nonlocality. We prove that for any finite speed, such models predict correlations that can be exploited for faster-than-light communication. This superluminal communication doesn’t require access to any hidden physical quantities, but only the manipulation of measurement devices at the level of our present-day description of quantum experiments. Consequently, all possible explanations of quantum correlations that satisfy the principle of continuity, which states that everything propagates gradually and continuously through space and time, or in other words, all combination of local common causes and direct causes that reproduce quantum correlations, lead to faster than light communication, which can be exploited by humans, at least in principle. Accordingly, either there is superluminal communication or the conclusion that Nature is nonlocal (i.e. discontinuous) is unavoidable.

1. Jean-Daniel Bancal, Stefano Pironio, Antonio Acin, Yeong-Cherng Liang, Valerio Scarani and Nicolas Gisin, Quantum non-locality based on finite-speed causal influences leads to superluminal signalling, Nature Physics, 8, 867-70, 2012. 2. N. Gisin, arXiv:1210.7308 3. Tomer Jack Barnea, Jean-Daniel Bancal, Yeong-Cherng Liang, Nicolas Gisin, A tripartite quantum state violating the hidden influence constraints, quant-ph/1304.1812, PRA in press.
MQIW02 16th October 2013
10:00 to 11:00
A Kent Continuous nonlocal games: why quantum nonlocality is not dominated
Co-author: Damian Pitalua-Garcia (DAMTP)

I will give an informal discussion of two recent papers. One, joint work with Damian Pitalua-Garcia, arXiv:1307.6839, describes a new approach to Bell inequalities for continuous sets of measurement choices, and new Bell inequalites.

The other, arXiv:1308.5009, reexamines Popescu and Rohrlich's discussion of the possibility of stronger nonlocal correlations than those allowed by quantum theory. It shows that no set of correlations is strictly more nonlocal than quantum correlations, in the sense that they violate all CHSH inequalities by at least as much as quantum theory does and some by more.

MQIW02 16th October 2013
11:30 to 12:30
Applications of non-reductive groups in Quantum Information Theory
We survey some ways that invariant theory and moment maps enter into quantum information theory, and emphasize how some non-traditional techniques, e.g., non-reductive actions, arise and are useful.
MQIW02 17th October 2013
09:00 to 10:00
JM Landsberg Recent contributions of algebraic geometry and representation theory to complexity theory
Algebraic geometry and representation theory have been used to prove lower bounds for the complexity of matrix multiplication, the complexity of linear circuits (matrix rigidity), and Geometric Complexity Theory (questions related to the conjecture that P is distinct from NP). Remarkably, these questions in computer science are related to classical questions in algebraic geometry regarding objects such as dual varieties, secant varieties, Darboux hypersurfaces, and classical intersection theory, as well as questions in representation theory such as the Foulkes-Howe conjecture and the asymptotic study of Kronecker coefficients. I will give an overview of my joint work with G. Ottaviani (matrix multiplication), L. Manivel and N. Ressayre (GCT) and F. Gesmundo, J. Hauenstein, and C. Ikenmeyer (linear circuits).
MQIW02 17th October 2013
10:00 to 11:00
The Challenges of Geometric Complexity Theory
It is a remarkable fact that two prominent problems of algebraic complexity theory, the permanent versus determinant problem and the tensor rank problem, can be restated as explicit orbit closure problems. This offers the potential for proving lower complexity bounds by relying on methods from algebraic geometry and representation theory. This basic idea for the tensor rank problem goes back to work by Volker Strassen from the mid eighties. It leads to challenging problems regarding the irreducible representions of symmetric groups over the complex numbers (tensor products and plethysms).

In the first part of the talk, we will present the general framework, explain some negative results, and state some open problems. Then we will move on to outline some recent progress for proving lower bounds on the border rank of the matrix multiplication tensor. This is achieved by the explicit construction of highest weight vectors vanishing on the (higher secant) varieties of tensors of border rank at most r.
MQIW02 17th October 2013
11:30 to 12:30
Multiplicities of representations of compact Lie groups, qualitative properties and some computations
Co-author: Baldoni Velleda (Roma Tor Vergata-Italy)

Let V be a representation space for a compact connected Lie group G decomposing as a sum of irreductible representations pi of G with finite multiplicity m(pi,V).

When V is constructed as the geometric quantization of a symplectic manifold with proper moment map, the multiplicity function pi-> m(pi,V)$is piecewise quasi polynomial on the cone of dominant weights. In particular, the function t-> m(t *pi,V) is a quasipolynomial,alonf the ray t*pi, when t runs over the non negative integers. We will explain how to compute effectively this quasi-polynomial (or the Duistermaat-Heckman measure) in some examples, including the function t-> c(t*lambda,t* mu,t*nu) for Clebsch-Gordan coefficients (in low rank) and the function t-> k(t*alpha,t*beta,t*gamma) for Kronecker-coefficients (with number of rows less or equal to 3). Our method is based on a multidimensional residue theorem (Jeffrey-Kirwan residues). MQIW02 17th October 2013 14:00 to 15:00 Pinning of Fermionic occupation numbers Co-authors: David Gross (University of Freiburg), Matthias Christandl (ETH Zurich) The problem of determining and describing the family of 1-particle reduced density operators (1-RDO) arising from N-fermion pure states (via partial trace) is known as the fermionic quantum marginal problem. We present its solution, a multitude of constraints on the eigenvalues of the 1-RDO, generalizing the Pauli exclusion principle. To explore the relevance of these constraints we study an analytically solvable model of N-fermions in a harmonic potential and determine the spectral trajectory' corresponding to the ground state as function of the fermion-fermion interaction strength. Intriguingly, we find that the occupation numbers are almost, but not exactly, pinned to the boundary of the allowed region. Our findings suggest a generalization of the Hartree-Fock approximation. MQIW02 17th October 2013 15:30 to 16:30 M Nakata The second-order reduced density matrices and its application to chemistry and physics Variational determination the ground state of two-particle Hamiltonian using the second-order reduced density matrix is very hopeful approach to quantum chemistry and condensed matter physics (J.Chem.Phys 114, 8282-8292 (2001)). The Quantum Marginal problem in this context is known as N-representability problem. If we employ some non-negativity conditions, which are necessary conditions of N-representability, the ground state energies are quite accurately calculated. In this talk, we show some results, and state some open questions to community. MQIW02 18th October 2013 09:00 to 10:00 MB Ruskai Uniqueness of pre-images of quantum marginals MQIW02 18th October 2013 10:00 to 11:00 Quantum marginals in quantum spin systems MQIW02 18th October 2013 11:30 to 12:30 B Terhal Different Circuit-to-Hamiltonian Constructions and their application for QMA MQIW02 18th October 2013 14:00 to 15:00 M Dalai Reliability of classical and classical-quantum channels The performance of a channel is usually measured in terms of its capacity C, intended as the largest rate achievable by block codes with probability of error which vanishes in the block-length. For rates R<C, the probability of error for optimal codes decreases exponentially fast with the block-length, and a more detailed measure of the performance of the channel is the so called reliability function E(R), the first order exponent of this error.Determining E(R) exactly is an unsolved problem in general; it includes as a sub-problem, for example, the determination of the zero-error capacity (also called Shannon capacity of a graph). In this talk, we discuss bounds to E(R) for classical and classical-quantum channels and presents some connections between those bounds and the Lovasz theta function. MQI 21st October 2013 11:00 to 12:00 Reasoning about postselection and complexity MQI 22nd October 2013 14:00 to 15:00 Structure and properties of the algebra of partially transposed operators We consider the structure of algebra of n-fold tensor product operators, partially transposed on the last term. Using purely algebraical methods we show that this algebra is semi-simple and then, considering its regular representation, we derive basic properties of the algebra. In particular we describe all irreducible representations of the algebra of partially transformed operators. It appears that there are two kinds of irreducible representations of the algebra. The first one is strictly connected with the representations of the group S(n-1) induced by irreducible representations of the group S(n-2). The second kind is structurally connected with irreducible representations of the group S(n-1). MQI 24th October 2013 14:00 to 15:00 The Second Laws of Quantum Thermodynamics The second law of thermodynamics tells us which state transformations are so statistically unlikely that they are effectively forbidden, and applies to systems composed of many particles. However, using tools from quantum information theory, we are seeing that one can make sense of thermodynamics in the regime where we only have a small number of particles interacting with a heat bath, or when we have highly correlated systems and wish to make non-statistical statements about them. Is there a second law of thermodynamics in this regime? Here, we find that for processes which are cyclic or very close to cyclic, the second law for microscopic or highly correlated systems takes on a very different form than it does at the macroscopic scale, imposing not just one constraint on what state transformations are possible, but an entire family of constraints. In particular, we find a family of quantum free energies which generalise the traditional ones, and show that they can never increase. The ordinary second law corresponds to the non-increasing of one of these free energies, with the remainder, imposing additional constraints on thermodynamic transitions of quantum systems. We further find that there are three regimes which govern which family of second laws govern state transitions, depending on how cyclic the thermodynamical process is. In one regime one can cause an apparent violation of the usual second law through a process of embezzling work from a large system which remains arbitrarily close to its original state. By making precise the definition of thermal operations, the laws of thermodynamics take on a simple form with the first law defining the class of thermal operations, the zeroeth law emerging as a unique equilibrium condition, and the remaining laws being a monotonicity property of our generalised free energies based on the Renyi-divergence. The derivations use tools from majorisation theory. MQI 29th October 2013 14:00 to 15:00 Does freedom of choice imply that the wave function is real? Q+ online seminar The question whether the quantum-mechanical wave function is "real" has recently attracted considerable interest. More precisely, the question is whether the wave function of a system is uniquely determined by any complete description of its "physical state". In this talk I will present a simple and self-contained proof that this is indeed the case, under an assumption that one may term "freedom of choice". It demands that arbitrary measurements can be applied to the system, and that these can be chosen independently of all parameters available at the time of measurement (with respect to any relativistic frame). A possible interpretation of this result is that the wave function of a system is as objective or real as any other complete description of the system's state. (This is based on unpublished work in collaboration with Roger Colbeck.) For video and slides, see: http://sites.google.com/site/plusquant/videos-of-previous-talks MQI 30th October 2013 14:00 to 15:00 Inequalities for the Ranks of Quantum States We investigate relations between the ranks of marginals of multipartite quantum states. These are the Schmidt ranks across all possible bipartitions and constitute a natural quantification of multipartite entanglement dimensionality. We show that there exist inequalities constraining the possible distribution of ranks. This is analogous to the case of von Neumann entropy (\alpha-R\'enyi entropy for \alpha=1), where nontrivial inequalities constraining the distribution of entropies (such as e.g. strong subadditivity) are known. It was also recently discovered that all other \alpha-R\'enyi entropies for$\alpha\in(0,1)\cup(1,\infty)$satisfy only one trivial linear inequality (non-negativity) and the distribution of entropies for$\alpha\in(0,1)\$ is completely unconstrained beyond non-negativity. Our result resolves an important open question by showing that also the case of \alpha=0 (logarithm of the rank) is restricted by nontrivial linear relations and thus the cases of von Neumann entropy (i.e., \alpha=1) and 0-R\'enyi entropy are exceptionally interesting measures of entanglement in the multipartite setting.
MQI 31st October 2013
14:00 to 15:00
Correlations, area laws, and stability of open and thermal many-body quantum systems
Investigating scaling laws of correlations and entanglement, stability and simulatability of quantum states on spin lattice systems is a central topic in Hamiltonian complexity theory. In this talk, we discuss open systems and thermal analogues of features of ground states of quantum many-body systems, using proof tools inspired by ideas of quantum information theory. For open systems, we establish a connection between mixing times - either captured by Liouvillian gaps or Log-Sobolev-constants independent of the system size - and the clustering of correlations and area laws. For Gibbs states, we prove that above a universal critical temperature only depending on local properties of the Hamiltonian's interaction hypergraph, thermal quantum states of local Hamiltonians are stable against distant Hamiltonian perturbations. As a consequence, local expectation values can be approximated in polynomial time. The stability theorem also provides a definition of temperature as a local quantity. We prove our clustering result via a reduction to a cluster expansion originally used to approximate thermal states by matrix product operators.
MQI 5th November 2013
14:00 to 15:00
</a><a href="https://www.ucl.ac.uk/quantum/UCL-ParisQuantumConnection"><b>No seminar due to UCL-Paris Quantum Connection event in London 4-5 November</a></b><a>
MQI 7th November 2013
14:00 to 15:00
R Werner Spectrum and propagation in electric quantum walks.
(joint work with A.H. Werner, C. Cedzich, D. Meschede, A. Alberti, T. Rybar. See arXiv:1302.2094 and arXiv:1302.2081, resp. PRL 111, 160601 and 110, 190601) I present a very simple quantum system, whose long time behavior depends extremely sensitively on a parameter E. (1) For rational E one sees some revivals (exponentially sharp in the denominator of E) followed ultimately by ballistic expansion. (2) For typical E (Lebesgue- almost all) one has localization with exponentially localized eigenfunctions, but there is also (3) a dense set of E for which one has hierarchical motion: An infinite hierarchy of time scales on each of which one has sharper and sharper revivals (with a repetition of everything before that) followed by larger and larger recursions. The spectrum of the walk operator is absolutely continuous, pure point, and singular continuous in these three cases. We also explain how on a fixed finite time scale these distinctions become irrelevant and it is enough to know an appropriate initial segment of the continued fraction expansion of E.
MQI 12th November 2013
14:00 to 15:00
Robust Characterization of Quantum Processes
Accurate characterization of quantum processes is critical for the scaling of quantum computing systems. Understanding the errors that occur in physical systems will both inform the design of future quantum computers and the design of error correcting codes. However, many characterization procedures suffer from systematic errors because they assume state preparation, measurement, and other controlling gates are error free. In this talk I will describe a method that can provide estimates of almost all parameters of a quantum map, yet is robust to many types of errors.
MQI 14th November 2013
14:00 to 15:00
P Shor A mod-p generalization of the CHSH game
We consider the following mod-p generalization of the CHSH game. Alice and Bob are each given a number, a and b, mod p. Alice must output x and Bob y so that x+y = ab mod p. We give some new bounds on the probability that Alice and Bob can win in both the classical and quantum games. This is joint work with Mohammad Bavarian.
MQI 19th November 2013
14:00 to 15:00
Device-independent radomness amplification with few devices and noise tolerance
MQI 21st November 2013
14:00 to 15:00
Efficient decoders for qudit topological codes
For a quantum error correcting code, a decoder is a (classical) algorithm, which given the set of measurement outcomes of the stabiliser generators of the code (the syndrome) outputs a set of unitarites which may be applied to correct the error. Since the mapping between errors and syndromes is not one-to-one, decoders attempt to output an operator which is most likely to correct the error, given the underlying error model. For the qubit toric code, the most widely used decoder is the Minimum Weight Perfect Matching algorithm. This decoder utilises some very special properties of the qubit toric code, it is not applicable, in general, to other topological codes. In [1] we introduce two decoders for the qudit (d>2) toric code. One of them is a generalisation of the decoder introduced by Bravyi and Haah [2] for the cubic code, and the other is a generalisation of an RG-based algorithm proposed by Duclos-Cianci and Poulin [3]. I will focus on the former in my talk, introducing the decoder, its limitations, and how those limitations can be overcome to produce an efficient and effective decoder for high d qudit toric codes. I will finish my talk by comparing the thresholds achieved with these different decoder strategies with a conjectured optimal threshold for these codes. [1] H. Anwar, B. Browne, E. T. Campbell, D.E. Browne, Efficient Decoders for Qudit Topological Codes, (to appear on the arxiv shortly). [2] Sergey Bravyi, Jeongwan Haah, Analytic and numerical demonstration of quantum self-correction in the 3D Cubic Code, arXiv:1112.3252 [3] Guillaume Duclos-Cianci, David Poulin, Fast Decoders for Topological Quantum Codes, Phys. Rev. Lett. 104 050504 (2010)
MQI 26th November 2013
14:00 to 15:00
Operator Systems, Tsirelson's Conjectures and Quantum Chromatic Numbers
MQIW04 27th November 2013
11:15 to 12:15
Boson sampling in the light of sampling complexity: A review
Boson sampling is a classically computationally hard problem that can - in principle - be efficiently solved with quantum linear optical networks. Recently this has lead to an experimental race to implement such devices. This talk will provide a review on the state of affairs concerning the possibility of certifying boson sampling devices. We discuss in detail several settings: 1. The use of symmetric and non-symmetric algorithms for distinguishing the boson sampling distribution from a particular other distribution. 2. Classical simulation of boson sampling in the presence of errors. 3. The impossibility of an efficient classical certification. We present some new results on estimating first and second moments of photon number distributions.
MQIW04 27th November 2013
13:30 to 14:30
Inverting well-conditioned matrices in Quantum Logspace
We show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. To the best of our knowledge the best classical algorithm for the problem requires Omega(log^2n) space. We also show how to approximate the spectrum of a normal matrix, or the singular values of an arbitrary matrix, with additive accuracy, and how to approximate the SVD decomposition of a matrix whose singular values are well separated.

The technique builds on ideas from several previous works, including simulating a Hamiltonian in small quantum space, treating a Hermitian matrix as a Hamiltonian and running the quantum phase estimation procedure on it (building on Harrow, Hassidim, and Lloyd) and making small space probabilistic (and quantum) computation consistent through the use of offline randomness and the shift and truncate method of Saks and Zhou.

MQIW04 27th November 2013
15:00 to 16:00
T Vidick A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
Co-authors: Zeph Landau (UC Berkeley), Umesh Vazirani (UC Berkeley)

Computing ground states of local Hamiltonians is a fundamental problem in condensed matter physics. We give the first randomized polynomial-time algorithm for finding ground states of gapped one-dimensional Hamiltonians: it outputs an (inverse-polynomial) approximation, expressed as a matrix product state (MPS) of polynomial bond dimension. The algorithm combines many ingredients, including recently discovered structural features of gapped 1D systems, convex programming, insights from classical algorithms for 1D satisfiability, and new techniques for manipulating and bounding the complexity of MPS. Our result provides one of the first major classes of Hamiltonians for which computing ground states is provably tractable despite the exponential nature of the objects involved.

Joint work with Zeph Landau and Umesh Vazirani.

MQIW04 27th November 2013
16:00 to 17:00
Complexity classification of local Hamiltonian problems
Co-author: Toby Cubitt (University of Cambridge)

The calculation of ground-state energies of physical systems can be formalised as the k-local Hamiltonian problem, which is the natural quantum analogue of classical constraint satisfaction problems. One way of making the problem more physically meaningful is to restrict the Hamiltonian in question by picking its terms from a fixed set S. Examples of such special cases are the Heisenberg and Ising models from condensed-matter physics.

In this talk I will discuss work which characterises the complexity of this problem for all 2-local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NP-complete; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1-local terms; for example, we prove for the first time QMA-completeness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1-local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2-local interactions: for any constant k, all k-local qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomial-time equivalent to the Ising model with transverse magnetic fields; or QMA-complete.

These results are a quantum analogue of Schaefer's dichotomy theorem for boolean constraint satisfaction problems.

MQIW04 28th November 2013
10:00 to 11:00
A variational eigenvalue solver on a quantum processor
Co-authors: Alberto Peruzzo (University of Sydney), Peter Shadbolt (University of Bristol), Man-Hong Yung (Tsinghua University), Xiao-Qi Zhou (University of Bristol), Peter Love (Haverford College), Alan Aspuru-Guzik (Harvard University), Jeremy O'Brien (University of Bristol)

Quantum computers promise to efficiently solve important problems that are intractable on a conventional computer. For quantum systems, where the dimension of the problem space grows exponentially, finding the eigenvalues of certain operators is one such intractable problem and remains a fundamental challenge. The quantum phase estimation algorithm can efficiently find the eigenvalue of a given eigenvector but requires fully coherent evolution. We present an alternative approach that greatly reduces the requirements for coherent evolution and we combine this method with a new approach to state preparation based on ans\"atze and classical optimization. We have implemented the algorithm by combining a small-scale photonic quantum processor with a conventional computer. We experimentally demonstrate the feasibility of this approach with an example from quantum chemistry: calculating the ground state molecular energy for He-H+, to within chemical accuracy. The proposed appro ach, by drastically reducing the coherence time requirements, enhances the potential of the quantum resources available today and in the near future.

MQIW04 28th November 2013
11:30 to 12:30
Probing Quantum Speedup in D-Wave Two
Co-authors: Sergio Boixo (Google Inc.), Sergei V. Isakov (Google Inc.), Zhihui Wang (ISI, University of California), Joshua Job (ISI, University of California), Daniel Lidar (ISI, University of California), John Martinis (Department of Physics, University of California), Matthias Troyer (ETH Zurich)

We are at a point where the first quantum devices are becoming available both in laboratories and commercially. While universal quantum computing still its infancy, analogue devices, such cold atoms experiments and quantum annealers, constitute the first step towards using quantum hardware for solving computational problems. In this talk, we show that D-Wave devices closely follows the statistics of simulated quantum annealing, whereas it is clearly different from semi-classical spin dynamics and classical thermal annealing. The theoretical study by Santoro [Science, Santoro et al., 295 (5564), 2427], where it was shown that quantum annealing outperforms classical thermal annealing, suggests that the D-Wave machines could have advantages over to classical hardware. We discuss how one probe for such advantages correctly, and we present preliminary results on the computational capabilities of the D-Wave devices.

MQIW04 28th November 2013
13:30 to 14:30
Graph Isomorphism: Quantum Ideas
MQIW04 28th November 2013
15:00 to 16:00
A constructive algorithm for the commutative Quantum Lovász Local Lemma
Co-authors: Martin Schwarz (University of Vienna), Frank Verstraete (University of Vienna)

The recently proven Quantum Lovász Local Lemma generalises the well-known Lovász Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the quantum kQSAT satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are never frustrated.

However, the QLLL only asserts existence; it says nothing about how to find the quantum state that satisfies the constraints. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the sought quantum state. As well as proving a constructive commutative QLLL, this provides a non-trivial poly-time example of a new type of "dissipative quantum algorithm".

MQI 3rd December 2013
14:00 to 15:00
S Massar Generalised Probabilistic Theories and the extension complexity of polytopes
In this work we present connections between the foundations of quantum mechanics, communication complexity, and the geometry of polytopes. Generalised Probabilistic Theories are a framework, described by a cone C and its dual C*, that allows generalisations of both classical and quantum theories. Communication complexity is the area of computers science that studies how much communication between two parties is necessary for them to solve specific tasks. We compare communication complexity when the states that are sent are classical, quantum, or states of a GPT. The existence of a randomised one-way communication complexity problems with positive outputs using classical (quantum) (GPT) states that produces on average the matrix M is equivalent to the linear (SDP) (cone) factorization of M. Polytopes arise in many areas of combinatorics. For instance solving the famous NP-complete Travelling Salesman Problem (TSP) is equivalent to linear optimisation over the corresponding TSP polytope. However many polytopes of interest (such as the TSP polytope) have exponentially many facets, which makes them intractable. An extended formulation of a polytope is a geometric object in a larger dimensional space whose projection onto the original space yields the desired polytope. Linear extensions of polytopes are given in terms of linear programs. Semi-definite and conic extensions of polytopes are given in terms of semi-definite positive (SDP) and conic programs. The extended formulation can sometimes be much simpler than the original polytope, hence the interest in extended formulations and the definition of the linear (SDP) (conic) extension complexity of a polytope as the size of the corresponding linear (SDP) (conic) program. The existence of a linear (SDP) (cone) extension of a polytope is equivalent to the cone factorisation of the slack matrix S of the polytope, and hence to a classical (quantum) (GPT) communication complexity problem. Using these connections, we show that all linear programs whose associated polytope projects to the traveling salesman polytope have exponential size. That is the linear extension complexity of the TSP polytope is exponential. The completely positive cone has a simple operational interpretation: it is the cone of density matrices obtained as convex combinations of quantum states with positive real coefficients. This cone is known to have an extremely complex geometry. All combinatorial polytopes, including the TSP polytope and any polytope whose vertices can be computed in polynomial time on a Turing machine, have polynomial size conic extension complexity when the cone is the completely positive cone. Using the connection with communication complexity, this implies an exponential gap between the communication complexity of GPT based on the completely positive cone and classical communication complexity, and a conjectured exponential gap with quantum communication complexity.
MQI 5th December 2013
14:00 to 15:00
One-shot entropies from thermodynamics
Long before their use in information theory, entropies have been introduced in thermodynamics. One may therefore wonder whether thermodynamics could also provide some guidance for the definition of one-shot entropies. It turns out that this is indeed the case: starting from an operational definition of entropy for thermal systems in the one-shot regime, we obtain a sensible entropy measure with applications in one-shot information theory. In particular, it automatically satisfies the data processing inequality and a chain rule. In my talk, I will show some recent advances as well as challenges of this research programme.
MQI 10th December 2013
14:00 to 15:00
Device-independent randomness extraction for arbitrarily weak min-entropy source
In this work we show how to use the GHZ Mermin inequality based devices to extract one bit of randomness from an (n,2) min-entropy source for arbitrary n. The extracted bit can be arbitrarily close to the uniform bit. The number of devices we use scales polynomially with n, what allows to tolerate (reasonably) imperfect GHZ devices.
MQI 12th December 2013
14:00 to 15:00
M Wilde Multiplicativity of completely bounded p-norms implies a strong converse for entanglement-assisted capacity
The fully quantum reverse Shannon theorem establishes the optimal rate of noiseless classical communication required for simulating the action of many instances of a noisy quantum channel on an arbitrary input state, while also allowing for an arbitrary amount of shared entanglement of an arbitrary form. Turning this theorem around establishes a strong converse for the entanglement-assisted classical capacity of any quantum channel. The present work proves the strong converse for entanglement-assisted capacity by a completely different approach. Namely, we exploit the recent entanglement-assisted "meta-converse" theorem of Matthews and Wehner, several properties of the recently established sandwiched Renyi relative entropy (also referred to as the quantum Renyi divergence), and the multiplicativity of completely bounded p-norms due to Devetak et al. The proof here demonstrates the extent to which the Arimoto approach can be helpful in proving strong converse theorems, it provides an operational relevance for the multiplicativity result of Devetak et al., and it adds to the growing body of evidence that the sandwiched Renyi relative entropy is the correct quantum generalization of the classical concept for all alpha > 1. This is joint work with Manish K. Gupta and is available as arXiv:1310.7028.
MQI 12th December 2013
16:00 to 17:00
P Hayden The computational complexity of entanglement detection
In quantum information, theorists and experimentalists alike are often acutely concerned with whether a given physical system is entangled or not. Recently, string theorists have acquired a similar morbid fascination because of catastrophic violations of monogamy of entanglement that seem to be caused by black holes. In this talk, I will explain how various formulations of the entanglement detection problem provide natural complete problems for a host of complexity classes including NP, BQP, QMA, QMA(2), QSZK and QIP. Moreover, entanglement detection provides a natural candidate for the first nontrivial complete problem for QIP(2). In some cases, the complexity depends subtly on the distance measure used, specifically the trace distance versus the 1-way LOCC distance. To conclude, I'll sketch how the difficulty of performing entanglement detection may help string theorists to sleep better at night. The talk will be based on joint work with Gus Gutoski, Daniel Harlow, Kevin Milner and Mark Wilde in the articles 1308.5788, 1301.4504 and 1211.6120.
MQI 16th December 2013
14:00 to 15:00
Non-Asymptotic Fundamental Limits and Gaussian Approximations for classical-quantum channels
MQI 17th December 2013
14:00 to 15:00
A solution of the Gaussian optimizer conjecture
The long-standing conjectures of the optimality of Gaussian inputs for Gaussian channel and Gaussian additivity are solved for a broad class of covariant or contravariant Bosonic Gaussian channels (which includes in particular thermal, additive classical noise, and amplifier channels) restricting to the class of states with finite second moments. We show that the vacuum is the input state which minimizes the entropy at the output of such channels. This allows us to show also that the classical capacity of these channels (under the input energy constraint) is additive and is achieved by Gaussian encodings.
MQI 17th December 2013
15:30 to 16:30
Potential capacity of quantum channels
MQIW05 23rd July 2018
09:45 to 10:30
Renato Renner 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.

MQIW05 23rd July 2018
11:00 to 11:45
Yiannis Kontoyiannis 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.
MQIW05 23rd July 2018
11:45 to 12:30
Joe Renes 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.

MQIW05 23rd July 2018
14:00 to 14:45
Guangyue Han 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.

MQIW05 23rd July 2018
14:45 to 15:30
Young-Han Kim 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

MQIW05 23rd July 2018
16:00 to 16:45
René Schwonnek 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.

MQIW05 23rd July 2018
16:45 to 17:30
Zahra Baghali Khanian 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.

MQIW05 24th July 2018
09:00 to 09:45
Tobias Koch 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).

MQIW05 24th July 2018
09:45 to 10:30
Ramji Venkataramanan 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)

MQIW05 24th July 2018
11:00 to 11:45
Philippe Faist 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]
MQIW05 24th July 2018
11:45 to 12:30
Kun Fang 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.
MQIW05 25th July 2018
09:00 to 09:45
Iman Marvian 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.

MQIW05 25th July 2018
09:45 to 10:30
Gerardo Adesso 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.

MQIW05 25th July 2018
11:00 to 11:45
Zi-Wen Liu Resource theory of quantum channels
MQIW05 25th July 2018
11:45 to 12:30
Mischa Woods 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.

MQIW05 26th July 2018
09:00 to 09:45
Pranab Sen 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.

MQIW05 26th July 2018
09:45 to 10:30
Oliver Johnson 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.

MQIW05 26th July 2018
11:00 to 11:45
Mario Berta 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.
MQIW05 26th July 2018
11:45 to 12:30
Felix Leditzky 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.

MQIW05 26th July 2018
14:00 to 14:45
Milan Mosonyi 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.

MQIW05 26th July 2018
14:45 to 15:30
Fumio Hiai 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.
MQIW05 26th July 2018
16:00 to 16:45
Anna Jenčová 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.
MQIW05 26th July 2018
16:45 to 17:30
Beth Ruskai 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.

MQIW05 27th July 2018
09:00 to 09:45
Ivan Bardet Functional inequalities and the study of the speed of decoherence of an open quantum system
MQIW05 27th July 2018
09:45 to 10:30
Sergii Strelchuk 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.

MQIW05 27th July 2018
11:00 to 11:45
Cambyse Rouzé 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.

MQIW05 27th July 2018
11:45 to 12:30
Ángela Capel 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.

MQIW05 27th July 2018
12:30 to 13:15
Marius Junge 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.