Thomas Vidick, Massachusetts Institute of Technology
Abstract
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. Recently the introduction of a new element, quantum entanglement, has brought a second life to the study of these games. Entanglement plays the role of a distributed resource that the players can tap in order to increase their odds of winning: how does its use affect the properties of the game? In turn, multiplayer games have proved a valuable tool in the study of fundamental properties 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. The proof is based on adapting the multilinearity test from Babai et al's seminal result MIP = NEXP [BFL'91] to the entangled-player setting.
In contrast with the hardness result I will also show that for some simple classes of two-player entangled games the maximum success probability can be approximated using a polynomial-size semidefinite program. The approximation algorithm is one of a growing family of examples demonstrating a deep connection that runs between the formalism of quantum mechanics and semidefinite programming. I will show how this connection can be further exploited by using the approximation algorithm for entangled games to obtain new approximation algorithms for purely classical problems in learning theory, such as robust principal component analysis.
Time permitting I will briefly discuss applications of entangled games to device-independent proofs of security in cryptography.