Chung, KaiMin ;
Wu, Xiaodi ;
Yuen, Henry
Parallel Repetition for Entangled kplayer Games via Fast Quantum Search
Abstract
We present two parallel repetition theorems for the entangled value of multiplayer, oneround free games (games where the inputs come from a product distribution). Our first theorem shows that for a kplayer free game G with entangled value val^*(G) = 1  epsilon, the nfold repetition of G has entangled value val^*(G^(\otimes n)) at most (1  epsilon^(3/2))^(Omega(n/sk^4)), where s is the answer length of any player. In contrast, the best known parallel repetition theorem for the classical value of twoplayer free games is val(G^(\otimes n)) <= (1  epsilon^2)^(Omega(n/s)), due to Barak, et al. (RANDOM 2009). This suggests the possibility of a separation between the behavior of entangled and classical free games under parallel repetition.
Our second theorem handles the broader class of free games G where the players can output (possibly entangled) quantum states. For such games, the repeated entangled value is upper bounded by (1  epsilon^2)^(Omega(n/sk^2)). We also show that the dependence of the exponent on k is necessary: we exhibit a kplayer free game G and n >= 1 such that val^*(G^(\otimes n)) >= val^*(G)^(n/k).
Our analysis exploits the novel connection between communication protocols and quantum parallel repetition, first explored by Chailloux and Scarpa (ICALP 2014). We demonstrate that better communication protocols yield better parallel repetition theorems: in particular, our first theorem crucially uses a quantum search protocol by Aaronson and Ambainis, which gives a quadratic Grover speedup for distributed search problems. Finally, our results apply to a broader class of games than were previously considered before; in particular, we obtain the first parallel repetition theorem for entangled games involving more than two players, and for games involving quantum outputs.
BibTeX  Entry
@InProceedings{chung_et_al:LIPIcs:2015:5072,
author = {KaiMin Chung and Xiaodi Wu and Henry Yuen},
title = {{Parallel Repetition for Entangled kplayer Games via Fast Quantum Search}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {512536},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5072},
URN = {urn:nbn:de:0030drops50727},
doi = {10.4230/LIPIcs.CCC.2015.512},
annote = {Keywords: Parallel repetition, quantum entanglement, communication complexity}
}
06.06.2015
Keywords: 

Parallel repetition, quantum entanglement, communication complexity 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

06.06.2015 