文章基本信息

标题：Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
本地全文：下载
作者：Andris Ambainis ; Janis Iraids
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：22
页码：146-156
DOI：10.4230/LIPIcs.TQC.2013.146
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Random Symmetric XOR games; Entanglement