The Taub Faculty of Computer Science Events and Talks

Multi-prover games have played a tremendous role in theoretical computer science over the last two decades. A lot of research effort went into determining how hard it is to approximate the value of such games, culminating in the celebrated PCP Theorem. When considering multi-prover games in the quantum world, the laws of quantum mechanics allow for a fascinating new effect: namely, the provers can share an arbitrary entangled state, on which they may perform any local measurements they like to help them answer the verifier's questions. One of the key open questions is to understand the expressive power of such games when the provers share entanglement.

We give an introduction and an overview of recent results in this area. We first show that the value of unique games is easy to approximate, implying that the unique games conjecture for entangled provers is false. We then show the first lower bound: It is NP-hard to decide if the entangled value of the game is 1. We proceed to show that approximating the value of such games to within a small epsilon is still NP hard. On the way we present the "almost commuting" versus "nearly commuting" conjecture which captures the bottleneck to improving epsilon.

No knowledge of quantum computing is required, I will introduce the necessary concepts.

Based on joint work with Hirotada Kobayashi, Keiji Matsumoto, Oded Regev, Ben Toner and Thomas Vidick.