Program

Invited Speakers

Accepted Talks

Accepted Posters

Timetable

Abstracts of invited talks:

Jop Briët (CWI, Amsterdam):
Entanglement-assisted Zero-error Source-channel Coding

This talk is about the use of entanglement in the classical zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way communication channel and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as few times as possible. The stiff zero-error constraint leads to beautiful connections to combinatorics (such as graph theory, the polynomial method and designs) and semidefinite programming (such as the celebrated Lovasz theta number). Our main result shows for the first time that shared entanglement can allow for an unbounded decrease in the asymptotic rate of classical source-channel codes.

Aram Harrow (MIT, Cambridge):
Separable states, the unique games conjecture and monogamy of entanglement

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 1205.4484 and 1210.6367.

Iordanis Kerenidis (CNRS -- Université Paris Diderot-Paris 7, Paris):
Quantum Communication Complexity

Communication complexity studies how much classical or quantum communication is necessary to solve a distributed task. It has numerous applications in computer science, including in data structures, circuit lower bounds, streaming algorithms, VLSI design, etc. In this model, two parties, Alice with input x and Bob with input y, collaborate to solve some computational problem that depends on both x and y. Their goal is to do this with minimal communication. The superiority of quantum communication has been proven in various models of communication complexity. Namely, there exist distributed computational problems that can be resolved with an exponentially smaller communication overhead by agents who have the ability to communicate via a quantum channel rather than a classical one. In the first part of the talk, we will review some of these separations and their wide-range applications, including for non-locality, quantum cryptography, quantum extractors etc. We will then focus on the different lower bound techniques for classical and quantum communication complexity and their respective power. We will see how the study of Bell inequality violations enables us to recast some well-known classical techniques in a more intuitive way and to prove new strong relations between communication and information complexity.

Thomas Vidick (MIT, Cambridge):
The Complexity of Entangled Games

Multiplayer games, from their use in cryptography to their role in the proof of the PCP theorem, play a central role in modern theoretical computer science. Players allowed to use entanglement can increase their odds of winning by exploiting its nonlocal correlations: how does it affect the properties of the game? What do games tell us about the fundamental strengths and limitations of entanglement? In this talk I will present some recent result on the complexity of entangled games. I will show that the class MIP*(3) of languages having three-prover entangled proof systems contains the class NEXP. This resolves a long-standing open question in quantum complexity by showing that entangled-prover proof systems are no less powerful than their classical counterparts. Building upon this characterization I will also present some recent results showing that approximating the largest possible violation by quantum mechanics of a tripartite Bell correlation inequality, within a factor (2-eps), is NP-hard. Since the largest possible violation of a bipartite correlation inequality can be computed in polynomial time, this result shows a striking complexity-theoretic distinction between bipartite and tripartite inequalities.

Stephanie Wehner (National University of Singapore, Singapore):
Two-party Quantum Cryptography - Results and Challenges

After long years of exchanging keys, Alice and Bob had a falling out and no longer trust each other. The goal of two-party quantum cryptography is to enable them to nevertheless solve tasks in cooperation. A classic example of such a task is bit commitment. Unfortunately, it has long been known that even using quantum communication, we cannot implement bit commitment perfectly. Is this the end for Alice and Bob? In this talk we will review the impossible, the possible and a number of assumptions that lead to security for two-party quantum cryptography. We will discuss some general properties of assumptions that yield security, and review some of the many exciting open problems in this area.