Henry Yuen: Parallel repetition for entangled games via fast quantum search
Wednesday, April 15, 2015 - 4:00pm to 5:00pm
Location:
32-G575
Speaker:
Henry Yuen
Biography:
MIT
Seminar group:
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.
Joint work with Kai-Min Chung and Xiaodi Wu.