License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.77
URN: urn:nbn:de:0030-drops-62073
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6207/
Go to the corresponding LIPIcs Volume Portal

Yuen, Henry

A Parallel Repetition Theorem for All Entangled Games

pdf-format:
LIPIcs-ICALP-2016-77.pdf (0.5 MB)

Abstract

The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Raz's classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known.

We prove that the entangled value of a two-player game G repeated n times in parallel is at most c_G*n^{-1/4}*log(n) for a constant c_G depending on G, provided that the entangled value of G is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.

BibTeX - Entry

@InProceedings{yuen:LIPIcs:2016:6207,
  author =	{Henry Yuen},
  title =	{{A Parallel Repetition Theorem for All Entangled Games}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{77:1--77:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6207},
  URN =		{urn:nbn:de:0030-drops-62073},
  doi =		{10.4230/LIPIcs.ICALP.2016.77},
  annote =	{Keywords: parallel repetition, direct product theorems, entangled games, quantum games}
}

Keywords: parallel repetition, direct product theorems, entangled games, quantum games
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI