The Taub Faculty of Computer Science Events and Talks
Sunday, 02.12.2007, 10:30
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
Based on joint work with Hirotada Kobayashi, Keiji Matsumoto, Oded
Regev, Ben Toner and Thomas Vidick.