New Mathematical Directions for Quantum Information
Monday 2nd September 2013 to Friday 6th September 2013
09:00 to 09:50  Registration  
09:50 to 10:00  Welcome by John Toland, Director of the Institute  
10:00 to 11:00 
T Vidick (Massachusetts Institute of Technology) 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. 
INI 1  
11:00 to 11:30  Morning Coffee  
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.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
14:00 to 15:00  Lecture 1: InformationTheoretic Techniques in ManyBody Physics  INI 1  
15:00 to 15:30  Afternoon Tea  
15:30 to 16:30 
A Harrow (Massachusetts Institute of Technology) 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 
INI 1  
16:30 to 17:30 
TS Cubitt (University of Cambridge) 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!). 
INI 1  
17:30 to 18:30  Wine reception and poster session 
09:00 to 10:00 
T Vidick (Massachusetts Institute of Technology) 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. 
INI 1  
10:00 to 11:00  Lecture 2: InformationTheoretic Techniques in ManyBody Physics  INI 1  
11:00 to 11:30  Morning Coffee  
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. 
INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
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.

INI 1  
15:00 to 15:30  Afternoon Tea  
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) 
INI 1  
16:30 to 17:30 
Open problems Chair: Andreas Winter 
INI 1 
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. 
INI 1  
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.

INI 1  
11:00 to 11:30  Morning Coffee  
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.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
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. 
INI 1  
15:00 to 15:30  Afternoon Tea  
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.

INI 1  
16:30 to 17:30  On spectral convergence bounds and the undecidability of control problems  INI 1 
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.

INI 1  
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. 
INI 1  
11:00 to 11:30  Morning Coffee  
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.

INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
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.

INI 1  
15:00 to 15:30  Afternoon Tea  
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.

INI 1  
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). 
INI 1  
19:30 to 22:00  Conference Dinner at Christ's College 
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.

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

INI 1  
11:00 to 11:30  Morning Coffee  
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). 
INI 1  
12:30 to 13:30  Lunch at Wolfson Court  
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.

INI 1  
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. 
INI 1  
15:00 to 15:30  Afternoon Tea  
15:30 to 16:30 
A Ambainis (University of Latvia) 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. 
INI 1  
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 
INI 1 