# Workshop Programme

## for period 2 - 6 September 2013

### New Mathematical Directions for Quantum Information

2 - 6 September 2013

Timetable

Monday 2 September | ||||

09:00-09:50 | Registration | |||

09:50-10:00 | Welcome by John Toland, Director of the Institute | |||

10:00-11:00 | Vidick, T (Massachusetts Institute of Technology) |
|||

Lecture 1: Entanglement in quantum interactive proofs (tutorial) | Sem 1 | |||

In the first lecture I will present the reasonably well-understood topic of entanglement in XOR games. We will review results by Tsirelson and Slofstra which provide lower and upper bounds on the dimension of entanglement required to play (near-)optimally. These results are obtained through connections with semidefinite programming and the theory of C*-algebras. In the second lecture I will move to more general classes of games. I will introduce an interesting "universal" class of entangled states, embezzlement states, and discuss some of their properties. I will present some lower bounds on entanglement dimension, leaving the proof of upper bounds as an exercise to the audience. Time permitting I will connect these results to the complexity theory of multi-prover interactive proofs. |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Mitchison, G (University of Cambridge) |
|||

Classical and quantum de Finetti theorems | Sem 1 | |||

This will be a basic tutorial on the classical and quantum de Finetti theorems, focussing on the finite versions of the theorem. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Brandao, F (University College London) |
|||

Lecture 1: Information-Theoretic Techniques in Many-Body Physics | Sem 1 | |||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Harrow, A (Massachusetts Institute of Technology) |
|||

Separable states, the unique games conjecture and monogamy of entanglement | Sem 1 | |||

Co-authors: Boaz Barak (MSR), Fernando Brandao (UCL), Jon Kelner (MIT), Ashley Montanaro (Bristol), David Steurer (Cornell), Yuan Zhou (CMU) The quantum separability problem---determining when a density matrix is entangled or when it is separable---is an old problem in quantum information theory. Although solving this problem to accuracy inverse-polynomial in dimension is NP-hard, only loose bounds are known on the complexity of the constant-error case. In this talk, I will describe some surprising connections between the quantum separability problem and a major open problem in classical computer science known as the unique games conjecture. Remarkably, even the proposed solutions to both problems turn out to be essentially the same, so that bounds on the monogamy of entanglement (aka de Finetti theorems) can be used to analyze the performance of classical algorithms. I will also describe conjectured monogamy bounds that are an alternate route to resolving the unique games conjecture. Based on 1001.0017, 1205.4484 and 1210.6367. Related Links •http://arxiv.org/abs/1001.0017 - Testing product states, quantum Merlin-Arthur games and tensor optimisation •http://arxiv.org/abs/1205.4484 - Hypercontractivity, Sum-of-Squares Proofs, and their Applications •http://arxiv.org/abs/1210.6367 - Quantum de Finetti Theorems under Local Measurements with Applications |
||||

16:30-17:30 | Cubitt, TS (University of Cambridge) |
|||

Undecidability of the spectral gap problem | Sem 1 | |||

Co-authors: David Perez-Garcia (Universidad Complutense de Madrid), Michael Wolf (Technische Universität München) The spectral gap of a quantum many-body Hamiltonian plays a crucial role in determining its physical properties. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring where the spectral gap vanishes. A number of longstanding open problems in mathematical physics, such as the Haldane conjecture or the 2D AKLT gap conjecture, concern spectral gaps of particular many-body models. In the related setting of quantum field theories, determining if Yang-Mills theory is gapped is one of the Millennium Prize Problems. Numerous important results about many-body Hamiltonians only apply to gapped systems. Determining when a model is gapped or gapless is therefore one of the primary goals of theoretical condensed matter physics. I will show that the spectral gap problem is unsolvable in general. Specifically, we prove that there exist translationally-invariant Hamiltonians on a 2D square lattice of finite-dimensional spins, with two-body nearest-neighbour interactions, for which the spectral gap problem is undecidable. This means that there exist Hamiltonians for which the presence or absence of a spectral gap cannot be proven in any consistent framework of mathematics. The proof is (of course!) by reduction from the Halting Problem. But the construction is complex, and draws on a wide variety of techniques: from quantum algorithms and quantum computing, to classical tiling problems, to recent Hamiltonian complexity results, to even more recent PEPS constructions. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for physics (which after all happens in the laboratory, not in Hilbert space!). |
||||

17:30-18:30 | Wine reception and poster session |

Tuesday 3 September | ||||

09:00-10:00 | Vidick, T (Massachusetts Institute of Technology) |
|||

Lecture 2: Entanglement in quantum interactive proofs (tutorial) | Sem 1 | |||

In the first lecture I will present the reasonably well-understood topic of entanglement in XOR games. We will review results by Tsirelson and Slofstra which provide lower and upper bounds on the dimension of entanglement required to play (near-)optimally. These results are obtained through connections with semidefinite programming and the theory of C*-algebras. In the second lecture I will move to more general classes of games. I will introduce an interesting "universal" class of entangled states, embezzlement states, and discuss some of their properties. I will present some lower bounds on entanglement dimension, leaving the proof of upper bounds as an exercise to the audience. Time permitting I will connect these results to the complexity theory of multi-prover interactive proofs. |
||||

10:00-11:00 | Brandao, F (University College London) |
|||

Lecture 2: Information-Theoretic Techniques in Many-Body Physics | Sem 1 | |||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Perez Garcia, D (Universidad Complutense de Madrid) |
|||

Lecture 1: Operator Space theory: a natural framework for Bell inequalities | Sem 1 | |||

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. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Nechita, IA (CNRS/Université de Toulouse) |
|||

Lecture 1: Random matrix theory with a view towards free probability, and connections to quantum information | Sem 1 | |||

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. |
||||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Leung, D (University of Waterloo) |
|||

The little we know about LOCC | Sem 1 | |||

Co-authors: Andrew Childs (University of Waterloo), Eric Chitambar (Southern Illinois University), Laura Mancinska (University of Waterloo), Maris Ozols (University of Waterloo), Andreas Winter (ICREA and Autonomus University of Barcelona) Consider the subset of multipartite quantum operations that can be implemented when the parties are restricted to using local quantum operations and classical communication (LOCC). We summarize recent results concerning LOCC -- in particular, what extra information processing tasks can be implemented (or not) if unlimited rounds of communication and vanishing error is allowed. We discuss extensions to the nonlocality without entanglement phenomenon. Joint works with Andrew Childs, Eric Chitambar, Laura Mancinska, Maris Ozols, Andreas Winter (plus additional results due to Matthias Kleinmann, Hermann Kampermann, Dagmar Bruss, Wei Cui, Hoi-Kwong Lo, Runyao Duan, and Min-Hsiu Hsieh) |
||||

Chair: Andreas Winter | ||||

16:30-17:30 | Open problems |

Wednesday 4 September | ||||

09:00-10:00 | Perez Garcia, D (Universidad Complutense de Madrid) |
|||

Lecture 2: Operator Space theory: a natural framework for Bell inequalities | Sem 1 | |||

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. |
||||

10:00-11:00 | Nechita, IA (CNRS/Université de Toulouse) |
|||

Lecture 2: Random matrix theory with a view towards free probability, and connections to quantum information | Sem 1 | |||

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. |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Keating, J (University of Bristol) |
|||

Lecture 1: A Primer in Random Matrix Theory | Sem 1 | |||

I will review some basic ideas and results in random matrix theory. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Datta, N (University of Cambridge) |
|||

Lecture 1: One-shot Quantum Information Theory I: Entropic Quantities | Sem 1 | |||

Optimal rates of quantum information-processing tasks, such as compression and transmission of information, and manipulation of entanglement, were initially obtained in the so-called "asymptotic, memoryless setting". In this setting, the underlying resources (e.g. information sources, channels and entanglement resources) are assumed to be memoryless, and to be available for asymptotically many uses. The optimal rates were shown to be given in terms of entropic quantities expressible in terms of the quantum relative entropy. In real-world communications and cryptographic systems, this setting is not generally valid: resources are used a finite number of times, and there may be correlations between their successive uses. Hence, it is important to evaluate the fundamental limits on information-processing tasks in the "one-shot setting", in which one considers a finite number of uses of arbitrary resources. In the first lecture, I will discuss entropic quantities which play an important role in the one-shot setting, highlighting their salient mathematical properties and operational significances. In the second lecture, I will focus on the problem of transmission of information through quantum channels, to illustrate how some of the entropic quantities (introduced in the first lecture) arise naturally in the one-shot setting. |
||||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Collins, B (University of Ottawa and AIMR) |
|||

Free compression norms and Lp norms | Sem 1 | |||

Co-authors: Serban Belinschi (Queen's), Ion Nechita (CNRS, Toulouse UPS) I will talk about a new norm that shows up naturally in the framework of random quantum channels. This norm relies on free probability theory and is called the free compression norm. We show that the problem of comparing it to Lp norms has applications to the understanding of the minimum output entropy (MOE) of typical quantum random channels. As an application, we establish violation of additivity of the MOE for typical quantum channels with Bell states, and find in this framework the optimal output dimension and the optimal violation. |
||||

16:30-17:30 | Wolf, M (Technische Universität München) |
|||

On spectral convergence bounds and the undecidability of control problems | Sem 1 |

Thursday 5 September | ||||

09:00-10:00 | Keating, J (University of Bristol) |
|||

Lecture 2: A Primer in Random Matrix Theory | Sem 1 | |||

I will review some basic ideas and results in random matrix theory. |
||||

10:00-11:00 | Datta, N (University of Cambridge) |
|||

Lecture 2: One-shot Quantum Information Theory II: Information Transmission | Sem 1 | |||

Optimal rates of quantum information-processing tasks, such as compression and transmission of information, and manipulation of entanglement, were initially obtained in the so-called "asymptotic, memoryless setting". In this setting, the underlying resources (e.g. information sources, channels and entanglement resources) are assumed to be memoryless, and to be available for asymptotically many uses. The optimal rates were shown to be given in terms of entropic quantities expressible in terms of the quantum relative entropy. In real-world communications and cryptographic systems, this setting is not generally valid: resources are used a finite number of times, and there may be correlations between their successive uses. Hence, it is important to evaluate the fundamental limits on information-processing tasks in the "one-shot setting", in which one considers a finite number of uses of arbitrary resources. In the first lecture, I will discuss entropic quantities which play an important role in the one-shot setting, highlighting their salient mathematical properties and operational significances. In the second lecture, I will focus on the problem of transmission of information through quantum channels, to illustrate how some of the entropic quantities (introduced in the first lecture) arise naturally in the one-shot setting. |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Dupuis, F (Aarhus Universitet) |
|||

A new definition for the quantum conditional Rényi entropy | Sem 1 | |||

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. |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-15:00 | Szarek, SJ (Case Western Reserve University) |
|||

Lecture 1: Concentration of measure (tutorial) | Sem 1 | |||

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. |
||||

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Santha, M (Université Paris 7 - Denis-Diderot) |
|||

Lecture 1 - Quantum walk and learning graph based algorithms (a tutorial) | Sem 1 | |||

In this talk I survey two generic methods to design quantum algorithms. I give an intuitive treatment of the discrete time quantization of classical Markov chains, and I describe nested walks, an extension of the model using quantum data structures. I explain the relatively recent idea of learning graphs, a combinatorial way to conceive quantum query algorithms. With several examples, including triangle and 3-collision finding, I illustrate the power of these methods. Finally I discuss time efficient implementations of learning graphs by quantum walks. |
||||

16:30-17:30 | Nagaj, D (Universität Wien) |
|||

Lecture 1: Introduction to Quantum Complexity (tutorial) | Sem 1 | |||

Coauthors: David Gosset, Sandeep Narayanaswami and Sean Hallgren In this and tomorrow's lecture, we will look at why frustrated (local Hamiltonian) and unfrustrated (quantum SAT) problems can be very hard to solve, even for the computers we don't have yet. The keywords are: universal computation, ground states, locality, qudits, promise gaps, eigenvalue gaps, history states, clocks, and translational invariance. The goal is to build the basics so that we can focus on recent ideas about the Quantum 3-SAT problem, random Quantum SAT (its SAT/UNSAT transition), perfect verifiers (QMA_1 vs QMA), quantum walks (the difficulty of solving scattering), blind quantum computation (limited power of QMA verifiers) and QMA vs. QCMA (MQA). |
||||

19:30-22:00 | Conference Dinner at Christ's College |

Friday 6 September | ||||

09:00-10:00 | Szarek, SJ (Case Western Reserve University) |
|||

Lecture 2: Concentration of measure (tutorial) | Sem 1 | |||

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. |
||||

10:00-11:00 | Santha, M (Université Paris 7 - Denis-Diderot) |
|||

Lecture 2 - Quantum walk and learning graph based algorithms (a tutorial) | Sem 1 | |||

In this talk I survey two generic methods to design quantum algorithms. I give an intuitive treatment of the discrete time quantization of classical Markov chains, and I describe nested walks, an extension of the model using quantum data structures. I explain the relatively recent idea of learning graphs, a combinatorial way to conceive quantum query algorithms. With several examples, including triangle and 3-collision finding, I illustrate the power of these methods. Finally I discuss time efficient implementations of learning graphs by quantum walks. |
||||

11:00-11:30 | Morning Coffee | |||

11:30-12:30 | Nagaj, D (Universität Wien) |
|||

Lecture 2: Introduction to Quantum Complexity (tutorial) | Sem 1 | |||

Coauthors: David Gosset, Sandeep Narayanaswami and Sean Hallgren In this and tomorrow's lecture, we will look at why frustrated (local Hamiltonian) and unfrustrated (quantum SAT) problems can be very hard to solve, even for the computers we don't have yet. The keywords are: universal computation, ground states, locality, qudits, promise gaps, eigenvalue gaps, history states, clocks, and translational invariance. The goal is to build the basics so that we can focus on recent ideas about the Quantum 3-SAT problem, random Quantum SAT (its SAT/UNSAT transition), perfect verifiers (QMA_1 vs QMA), quantum walks (the difficulty of solving scattering), blind quantum computation (limited power of QMA verifiers) and QMA vs. QCMA (MQA). |
||||

12:30-13:30 | Lunch at Wolfson Court | |||

14:00-14:30 | Eisert, J (Freie Universität Berlin) |
|||

Boson-Sampling in the light of sample complexity | Sem 1 | |||

Boson-Sampling is a classically computationally hard problem that can - in principle - be efficiently solved with linear quantum optical networks. Very recently, a rush of experimental activity has ignited with the aim of developing such devices as feasible instances of quantum simulators. Even approximate Boson-Sampling is believed to be hard with high probability if the unitary describing the optical network is drawn from the Haar measure. In this work we show that in this setup, with probability exponentially close to one in the number of bosons, no symmetric algorithm can distinguish the Boson-Sampling distribution from the uniform one from fewer than exponentially many samples. This means that the two distributions are operationally indistinguishable without detailed a priori knowledge. We carefully discuss the prospects of efficiently using knowledge about the implemented unitary for devising non-symmetric algorithms that could potentially improve upon this. We conclude that due to the very fact that Boson-Sampling is believed to be hard, efficient classical certification of Boson-Sampling devices seems to be out of reach. |
||||

14:30-15:00 | Strelchuk, S (University of Cambridge) |
|||

Entanglement recycling and generalized teleportation | Sem 1 | |||

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

15:00-15:30 | Afternoon Tea | |||

15:30-16:30 | Ambainis, A (University of Latvia) |
|||

Exact quantum algorithms | Sem 1 | |||

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. |
||||

16:30-17:30 | Gross, D (Universität Freiburg) |
|||

Quantum Information for Optical Microscopy | Sem 1 | |||

Co-authors: Richard Küng (University of Freiburg), Felix Krahmer (University of Goettingen) Optical sensors pick up the intensity of light fields, but are insensitive to phase. It is, however, conceivable that an "overcomplete" set of intensity measurements may allow one to reconstruct the complete state of the light field emanating from a given object. In the past two years, stable algorithms with rigorous performance guarantees for this "phase recovery problem" have been developed. They are ultimately based on low-rank matrix recovery algorithms whose technical analysis has benefited from methods originating in quantum information. I will review these developments and present new results towards the de-randomization of phase estimation protocols. Related Links: •http://www.qc.uni-freiburg.de - group home page |