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.TQC.2013.146
URN: urn:nbn:de:0030-drops-43156
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4315/
Go to the corresponding LIPIcs Volume Portal

Ambainis, Andris ; Iraids, Janis

Provable Advantage for Quantum Strategies in Random Symmetric XOR Games

pdf-format:
23.pdf (0.4 MB)

Abstract

Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of n players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any n-player symmetric XOR game the entangled value of the game is Theta((sqrt(ln(n)))/(n^{1/4})) adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is Theta(sqrt(ln(n))) for almost any symmetric XOR game.

BibTeX - Entry

@InProceedings{ambainis_et_al:LIPIcs:2013:4315,
  author =	{Andris Ambainis and Janis Iraids},
  title =	{{Provable Advantage for Quantum Strategies in Random Symmetric XOR Games}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{146--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Simone Severini and Fernando Brandao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4315},
  URN =		{urn:nbn:de:0030-drops-43156},
  doi =		{10.4230/LIPIcs.TQC.2013.146},
  annote =	{Keywords: Random Symmetric XOR games, Entanglement}
}

Keywords: Random Symmetric XOR games, Entanglement
Collection: 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)
Issue Date: 2013
Date of publication: 13.11.2013

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