Videos and presentation materials from other INI events are also available.
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 wellunderstood 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 multiprover 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: InformationTheoretic Techniques in ManyBody Physics  
MQIW01 
2nd September 2013 15:30 to 16:30 
A Harrow 
Separable states, the unique games conjecture and monogamy of entanglement
Coauthors: Boaz Barak (MSR), Fernando Brandao (UCL), Jon Kelner (MIT), Ashley Montanaro (Bristol), David Steurer (Cornell), Yuan Zhou (CMU)
The quantum separability problemdetermining when a density matrix is entangled or when it is separableis an old problem in quantum information theory. Although solving this problem to accuracy inversepolynomial in dimension is NPhard, only loose bounds are known on the complexity of the constanterror 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 MerlinArthur games and tensor optimisation •http://arxiv.org/abs/1205.4484  Hypercontractivity, SumofSquares 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
Coauthors: David PerezGarcia (Universidad Complutense de Madrid), Michael Wolf (Technische Universität München)
The spectral gap of a quantum manybody 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 manybody models. In the related setting of quantum field theories, determining if YangMills theory is gapped is one of the Millennium Prize Problems. Numerous important results about manybody 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 translationallyinvariant Hamiltonians on a 2D square lattice of finitedimensional spins, with twobody nearestneighbour 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 wellunderstood 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 multiprover interactive proofs. 

MQIW01 
3rd September 2013 10:00 to 11:00 
Lecture 2: InformationTheoretic Techniques in ManyBody 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
Coauthors: 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, HoiKwong Lo, Runyao Duan, and MinHsiu 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: Oneshot Quantum Information Theory I: Entropic Quantities
Optimal rates of quantum informationprocessing tasks, such as compression and transmission of information, and manipulation of entanglement, were initially obtained in the socalled "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 realworld 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 informationprocessing tasks in the "oneshot 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 oneshot 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 oneshot setting. 

MQIW01 
4th September 2013 15:30 to 16:30 
Free compression norms and Lp norms
Coauthors: 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: Oneshot Quantum Information Theory II: Information Transmission
Optimal rates of quantum informationprocessing tasks, such as compression and transmission of information, and manipulation of entanglement, were initially obtained in the socalled "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 realworld 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 informationprocessing tasks in the "oneshot 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 oneshot 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 oneshot 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 3collision 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 3SAT 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 3collision 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 3SAT 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 
BosonSampling in the light of sample complexity
BosonSampling 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 BosonSampling 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 BosonSampling 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 nonsymmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that BosonSampling is believed to be hard, efficient classical certification of BosonSampling devices seems to be out of reach.


MQIW01 
6th September 2013 14:30 to 15:00 
Entanglement recycling and generalized teleportation
Coauthors: 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 portbased 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. Portbased 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
Coauthors: 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 lowrank 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 derandomization of phase estimation protocols. Related Links: •http://www.qc.unifreiburg.de  group home page 

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 twoqubit state discrimination?  
MQI 
19th September 2013 14:00 to 15:00 
A Cabello  A graphtheoretic 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 PopescuRohrlich boxes and random access codes
We study a problem of interconvertibility of two supraquantum resources: one is so called PRbox, 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 PRbox supplemented with one bit of communication can be used to simulate RAC. We ask the converse question: to what extent RAC can simulate PRbox? To this end we introduce "racbox": a box such that supplemented with one bit of communication offers RAC. As said, PRbox can simulate racbox. The question we raise, is whether any racbox can simulate PRbox. We show that a nonsignaling racbox indeed can simulate PRbox, hence those two resources are equivalent. We also provide an example of signalling racbox which cannot simulate PRbox. We give a resource inequality between racboxes and PRboxes, 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 realvectorspace variant of quantum theory. I show how a particular model within realvectorspace 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 
ZeroError Classical Channel Capacity and Simulation Cost Assisted by Quantum NonSignalling Correlations
We study the oneshot zeroerror classical capacity of quantum channels assisted by quantum nonsignalling correlations, and the reverse problem of exact simulation. Both lead to simple semidefinite programmings whose solutions can be given in terms of the conditional minentropies. We show that the asymptotic simulation cost is precisely the conditional minentropy of the ChoiJamiolkowski matrix of the given channel. For classicalquantum 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 zeroerror classical capacity of a graph assisted by quantum nonsignalling 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
Coauthor: 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
Coauthors: 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 highdimensional 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 informationprocessing 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 normlike quantities. In applications noisy quantum channels arise from irreversible evolutions of open quantum systems interacting with environmenta 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 informationprocessing 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 tensorproduct 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 NonLocality
Coauthors: Rafael Chaves (University of Freiburg), Lukas Luft (University of Freiburg)
The fields of quantum nonlocality 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 nonconvex 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 typesclassifying strings according to letter frequenciesis 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 kpositive maps (ongoing, joint with Hayden and Nechita).


MQIW02 
15th October 2013 15:30 to 16:30 
Threshold phenomena for quantum marginals
Coauthors: 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 ABmarginal 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 lesstechnical 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 spacelike 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 fasterthanlight 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 presentday 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. JeanDaniel Bancal, Stefano Pironio, Antonio Acin, YeongCherng Liang, Valerio Scarani and Nicolas Gisin, Quantum nonlocality based on finitespeed causal influences leads to superluminal signalling, Nature Physics, 8, 86770, 2012. 2. N. Gisin, arXiv:1210.7308 3. Tomer Jack Barnea, JeanDaniel Bancal, YeongCherng Liang, Nicolas Gisin, A tripartite quantum state violating the hidden influence constraints, quantph/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
Coauthor: Damian PitaluaGarcia (DAMTP)
I will give an informal discussion of two recent papers. One, joint work with Damian PitaluaGarcia, 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 nonreductive groups in Quantum Information Theory
We survey some ways that invariant theory and moment maps enter into quantum information theory, and emphasize how some nontraditional techniques, e.g., nonreductive 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 FoulkesHowe 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
Coauthor: Baldoni Velleda (Roma Tor VergataItaly)
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 quasipolynomial (or the DuistermaatHeckman measure) in some examples, including the function t> c(t*lambda,t* mu,t*nu) for ClebschGordan coefficients (in low rank) and the function t> k(t*alpha,t*beta,t*gamma) for Kroneckercoefficients (with number of rows less or equal to 3). Our method is based on a multidimensional residue theorem (JeffreyKirwan residues).


MQIW02 
17th October 2013 14:00 to 15:00 
Pinning of Fermionic occupation numbers
Coauthors: David Gross (University of Freiburg), Matthias Christandl (ETH Zurich)
The problem of determining and describing the family of 1particle reduced density operators (1RDO) arising from Nfermion 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 1RDO, generalizing the Pauli exclusion principle. To explore the relevance of these constraints we study an analytically solvable model of Nfermions in a harmonic potential and determine the spectral `trajectory' corresponding to the ground state as function of the fermionfermion 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 HartreeFock approximation.


MQIW02 
17th October 2013 15:30 to 16:30 
M Nakata 
The secondorder reduced density matrices and its application to chemistry and physics
Variational determination the ground state of twoparticle Hamiltonian using the secondorder reduced density matrix is very hopeful approach to quantum chemistry and condensed matter physics (J.Chem.Phys 114, 82828292 (2001)). The Quantum Marginal problem in this context is known as Nrepresentability problem. If we employ some nonnegativity conditions, which are necessary conditions of Nrepresentability, 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 preimages 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 CircuittoHamiltonian Constructions and their application for QMA  
MQIW02 
18th October 2013 14:00 to 15:00 
M Dalai 
Reliability of classical and classicalquantum 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 blocklength. For rates R<C, the probability of error for optimal codes decreases exponentially fast with the blocklength, 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 subproblem, for example, the determination of the zeroerror capacity (also called Shannon capacity of a graph). In this talk, we discuss bounds to E(R) for classical and classicalquantum 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 nfold tensor product operators, partially transposed on the last term. Using purely algebraical methods we show that this algebra is semisimple 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(n1) induced by irreducible representations of the group S(n2). The second kind is structurally connected with irreducible representations of the group S(n1).


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 nonstatistical 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 nonincreasing 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 Renyidivergence. 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 quantummechanical 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 selfcontained 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/videosofprevioustalks 

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 (\alphaR\'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 \alphaR\'enyi entropies for $\alpha\in(0,1)\cup(1,\infty)$ satisfy only one trivial linear inequality (nonnegativity) and the distribution of entropies for $\alpha\in(0,1)$ is completely unconstrained beyond nonnegativity. 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 0R\'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 manybody 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 manybody 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 LogSobolevconstants 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/UCLParisQuantumConnection"><b>No seminar due to UCLParis Quantum Connection event in London 45 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 modp generalization of the CHSH game
We consider the following modp 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 
Deviceindependent 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 onetoone, 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 RGbased algorithm proposed by DuclosCianci 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 selfcorrection in the 3D Cubic Code, arXiv:1112.3252
[3] Guillaume DuclosCianci, 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 nonsymmetric 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 wellconditioned 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 polynomialtime algorithm for the ground state of 1D gapped local Hamiltonians
Coauthors: 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 polynomialtime algorithm for finding ground states of gapped onedimensional Hamiltonians: it outputs an (inversepolynomial) 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
Coauthor: Toby Cubitt (University of Cambridge)
The calculation of groundstate energies of physical systems can be formalised as the klocal 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 condensedmatter physics. In this talk I will discuss work which characterises the complexity of this problem for all 2local qubit Hamiltonians. Depending on the subset S, the problem falls into one of the following categories: in P; NPcomplete; polynomialtime equivalent to the Ising model with transverse magnetic fields; or QMAcomplete. The third of these classes contains NP and is contained within StoqMA. The characterisation holds even if S does not contain any 1local terms; for example, we prove for the first time QMAcompleteness of the Heisenberg and XY interactions in this setting. If S is assumed to contain all 1local terms, which is the setting considered by previous work, we have a characterisation that goes beyond 2local interactions: for any constant k, all klocal qubit Hamiltonians whose terms are picked from a fixed set S correspond to problems either in P; polynomialtime equivalent to the Ising model with transverse magnetic fields; or QMAcomplete. 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
Coauthors: Alberto Peruzzo (University of Sydney), Peter Shadbolt (University of Bristol), ManHong Yung (Tsinghua University), XiaoQi Zhou (University of Bristol), Peter Love (Haverford College), Alan AspuruGuzik (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 smallscale 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 HeH+, 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 DWave Two
Coauthors: 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 DWave devices closely follows the statistics of simulated quantum annealing, whereas it is clearly different from semiclassical 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 DWave 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 DWave 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
Coauthors: Martin Schwarz (University of Vienna), Frank Verstraete (University of Vienna)
The recently proven Quantum Lovász Local Lemma generalises the wellknown 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 manybody 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 nontrivial polytime 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 oneway 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 NPcomplete 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. Semidefinite and conic extensions of polytopes are given in terms of semidefinite 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 
Oneshot 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 oneshot entropies. It turns out that this is indeed the case: starting from an operational definition of entropy for thermal systems in the oneshot regime, we obtain a sensible entropy measure with applications in oneshot 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 
Deviceindependent randomness extraction for arbitrarily weak minentropy 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) minentropy 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 pnorms implies a strong converse for entanglementassisted 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 entanglementassisted classical capacity of any quantum channel. The present work proves the strong converse for entanglementassisted capacity by a completely different approach. Namely, we exploit the recent entanglementassisted "metaconverse" 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 pnorms 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 1way 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 
NonAsymptotic Fundamental Limits and Gaussian Approximations for classicalquantum channels  
MQI 
17th December 2013 14:00 to 15:00 
A solution of the Gaussian optimizer conjecture
The longstanding 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 “BeyondIID”version of the Asymptotic Equipartition Property. It asserts
that the smooth minentropy 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 nonasymptotic 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 informationtheoretic and
codingtheoretic points of view. In the former, we give a oneshot
characterization of the optimal rate of privacy amplification against classical
adversaries in terms of the optimal typeII error in asymmetric hypothesis
testing. This formulation can be easily computed to give finiteblocklength
bounds and turns out to be equivalent to smooth minentropy 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 errorcorrecting 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 (selfdual) erasure channel observed by Martinian and
Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results
on optimal lossy compression by polar and lowdensity generator matrix codes. 

MQIW05 
23rd July 2018 14:00 to 14:45 
Guangyue Han 
InformationTheoretic Extensions of the ShannonNyquist Sampling Theorem
This talk will present informationtheoretic extensions of the classical ShannonNyquist sampling theorem and some of their applications. More specifically, we consider a continuoustime 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 ShannonNyquist sampling theorem, where the original continuoustime channel is converted to an equivalent discretetime 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 continuoustime 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 continuoustime white Gaussian channel. Nevertheless, as opposed to the white Gaussian noise formulation, a link that establishes the informationtheoretic connection between a continuous time channel under the Brownian motion formulation and its discretetime counterparts has long been missing. This paper is to fill this gap by establishing causalitypreserving connections between continuoustime Gaussian feedback/memory channels and their associated discretetime versions in the forms of sampling and approximation theorems, which we believe will help to contribute the further development of continuoustime information theory. Related Links 

MQIW05 
23rd July 2018 14:45 to 15:30 
YoungHan 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 ratedistortion and capacity. The key idea behind this
extension is the ergodic decomposition of stationary processes, which was
utilized earlier by Gallager for ratedistortion 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 pointtopoint 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 quantumclassical 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
SlepianWolf
theorem.
We focus specifically on quantumclassical (qc)
sources,
for which one point of the rate region was
previously
determined by Devetak and Winter. Whereas the
Devetak
Winter point attains a ratesum 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
singleletter,
but still asymptotic, converse.


MQIW05 
24th July 2018 09:00 to 09:45 
Tobias Koch 
Rényi’s Information Dimension Beyond I.I.D.
Coauthor: Bernhard C. Geiger (Graz University of Technology) In 1959, Rényi proposed the information dimension and the ddimensional 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 ratedistortion theory, almost lossless analog compression, or the analysis of interference channels. In this talk, I will propose a generalization of information dimension to stochastic processes, termed information dimension rate. I will then discuss some of its properties and compare it with other generalizations of information dimension available in the literature. I will further show that for Gaussian processes the information dimension rate permits a simple and intuitive characterization in terms of its spectral distribution function.Joint work with Bernhard Geiger (Graz University of Technology). Related Links


MQIW05 
24th July 2018 09:45 to 10:30 
Ramji Venkataramanan 
Strong converses and highdimensional 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 informationtheoretic 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
informationtheoretic 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/18EJS14) 

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 singleletter 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 Gibbspreserving 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 timecovariant quantum processes or when restricting to independent and identical inputs. In our derivations we make extensive use of SchurWeyl duality and informationtheoretic 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 MaxInformation
Coauthors: 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 oneshot quantum simulation cost under nosignalling assisted codes are efficiently computable via semidefinite programming. Second, we introduce the channel's smooth maxinformation, which can be seen as a oneshot generalization of the mutual information of a quantum channel. We provide an exact operational interpretation of the channel's smooth maxinformation as the oneshot quantum simulation cost. Third, we derive the asymptotic equipartition property (AEP) of the channel's smooth maxinformation, 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 nosignalling 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 wellunderstood 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 nonzero 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
(fullrank) 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
Coauthors: 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 continuousvariable Gaussian states and Gaussian operations, establishing methods for their description and quantification. We show in particular that, under a few intuitive and physicallymotivated assumptions on the set of free states, no Gaussian quantum resource can be distilled with free Gaussian operations, even when an unlimited supply of the resource state is available. This places fundamental constraints on state transformations in all such Gaussian resource theories. We discuss in particular the applications to quantum entanglement, where we extend previously known results by showing that Gaussian entanglement cannot be distilled even with Gaussian operations preserving the positivity of the partial transpose, as well as to other Gaussian resources such as steering and optical nonclassicality. A unified semidefinite programming representation of all these reso urces is provided. Related Links


MQIW05 
25th July 2018 11:00 to 11:45 
ZiWen 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 backaction 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
backreaction 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 socalled `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 socalled `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 oneshot 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 oneshot 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 wellknown 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 logSobolev
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 logconcavity.


MQIW05 
26th July 2018 11:00 to 11:45 
Mario Berta 
Partially smoothed information measures
Smooth entropies are a tool for quantifying resource
tradeoffs in (quantum) information theory and cryptography. In typical bi and
multipartite problems, however, some of the subsystems 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
subsystems fixed. This partial smoothing of information measures naturally
allows to give more refined characterizations of various informationtheoretic
problems in the oneshot setting. In particular, we immediately get asymptotic
secondorder characterizations for tasks such as privacy amplification against
classical side information or classical state splitting. For quantum problems
like state merging the general resource tradeoff is tightly characterized by
partially smoothed information measures as well. However, for quantum systems
we can so far only give the asymptotic firstorder 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 twoletter level, a substantial gap between the
threshold for zero quantum capacity and zero singleletter coherent
information, a big gap between singleletter 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 muchneeded
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 fdivergences in von Neumann algebras
This talk is a comprehensive survey on recent developments of quantum divergences in general von Neumann algebras, including standard fdivergences, maximal fdivergences, and R\'enyi type divergences, whose mathematical backgrounds are Haagerup's L^pspaces and Araki's relative modular operator. Standard fdivergences were formerly studied by Petz in a bit more general form with name quasientropy, 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 fdivergence, from which most important properties of standard fdivergences follow immediately. We also go into standard R\'enyi divergences (as a variation of standard fdivergences) 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 BertaScholzTomamichel. Finally, we treat maximal fdivergences and discuss their definition, integral expression, and comparison with standard fdivergences. 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_pspaces
The standard quantum Renyi relative entropies belong to the class of Petz quantum fdivergences 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 fdivergences 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 noncommutative L_pspaces 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 ArakiMasuda 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 maxmin 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 wellknown 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 logSobolev 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
logconcavity.


MQIW05 
27th July 2018 11:00 to 11:45 
Cambyse Rouzé 
Quantum reverse hypercontractivity: its tensorization and application to strong converses
Hypercontractivity and logSobolev 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 logSobolev 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 QuasiFactorization of the relative entropy
The existence of a positive logSobolev 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
quasifactorization of the entropy in terms of the conditional entropy in some subalgebras. In this work we analyze analogous quasifactorization results in the quantum case. For that, we dene the quantum conditional relative entropy and prove several quasifactorization results for it. As an illustration of their potential, we use one of them to obtain a positive logSobolev constant for the heatbath 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 logsobolev 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 matrixvalued setting,
similar to results by Bardet and collaborators.
