Spring 2015

Parallel Repetition for Entangled Games via Fast Quantum Search

Wednesday, April 22nd, 2015 3:30 pm4:00 pm

Add to Calendar

We give improved parallel repetition theorems for multiplayer, one-round games with entangled players, when the inputs to the players are uncorrelated. We do so by exploiting a novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa: by taking advantage of fast quantum protocols for distributed search, we show that for this class of games (called free games), the entangled value of the n-fold repetition decays as (1 - eps^{3/2})^{\Omega(n/s)}, where 1 - eps is the entangled value of the original game, and s is the output alphabet size.

In contrast, the best known parallel repetition theorem for free games (due to Barak, et al.) in the classical setting is that the n-fold repetition value is bounded by (1 -eps^2)^{\Omega(n/s)}, suggesting the possibility of a separation between the behavior of quantum and classical games under parallel repetition.

Our proof takes advantage of the Aaronson-Ambainis quantum search protocol, and a general theorem of Nayak and Salzman that bounds the ability of parties to convey classical messages using two-way quantum communication. No prior knowledge of quantum information will be assumed.

Joint work with Kai-Min Chung and Xiaodi Wu.