A Caltech Library Service

Explicit Lower and Upper Bounds on the Entangled Value of Multiplayer XOR Games

Briët, Jop and Vidick, Thomas (2013) Explicit Lower and Upper Bounds on the Entangled Value of Multiplayer XOR Games. Communications in Mathematical Physics, 321 (1). pp. 181-207. ISSN 0010-3616. doi:10.1007/s00220-012-1642-5.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The study of quantum-mechanical violations of Bell inequalities is motivated by the investigation, and the eventual demonstration, of the nonlocal properties of entanglement. In recent years, Bell inequalities have found a fruitful re-formulation using the language of multiplayer games originating from Computer Science. This paper studies the nonlocal properties of entanglement in the context of the simplest such games, called XOR games. When there are two players, it is well known that the maximum bias—the advantage over random play—of players using entanglement can be at most a constant times greater than that of classical players. Recently, Pérez-García et al. (Commun. Mathe. Phys. 279:455, 2008) showed that no such bound holds when there are three or more players: the use of entanglement can provide an unbounded advantage, and scale with the number of questions in the game. Their proof relies on non-trivial results from operator space theory, and gives a non-explicit existence proof, leading to a game with a very large number of questions and only a loose control over the local dimension of the players’ shared entanglement. We give a new, simple and explicit (though still probabilistic) construction of a family of three-player XOR games which achieve a large quantum-classical gap (QC-gap). This QC-gap is exponentially larger than the one given by Pérez-García et. al. in terms of the size of the game, achieving a QC-gap of order √N with N^2 questions per player. In terms of the dimension of the entangled state required, we achieve the same (optimal) QC-gap of √N for a state of local dimension N per player. Moreover, the optimal entangled strategy is very simple, involving observables defined by tensor products of the Pauli matrices. Additionally, we give the first upper bound on the maximal QC-gap in terms of the number of questions per player, showing that our construction is only quadratically off in that respect. Our results rely on probabilistic estimates on the norm of random matrices and higher-order tensors which may be of independent interest.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2012 Springer-Verlag Berlin Heidelberg. Received: 16 March 2012; Accepted: 10 May 2012; Published online: 19 December 2012. We thank Harry Buhrman, Carlos Palazuelos, David Perez-Garcia, Gilles Pisier, Oded Regev, Ignacio Villanueva and Ronald deWolf for useful discussions. T.V. is grateful to CWI for hosting him while part of this work was done. J.B. thanks Universidad Complutense for hosting him while part of this work was done. We thank the anonymous referees for their many helpful comments. T.V. is supported by the National Science Foundation under Grant No. 0844626. J.B. is supported by an NWO Vici grant and the EU project QCS.
Funding AgencyGrant Number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)UNSPECIFIED
Issue or Number:1
Record Number:CaltechAUTHORS:20160318-154623344
Persistent URL:
Official Citation:Briët, J., Vidick, T. Explicit Lower and Upper Bounds on the Entangled Value of Multiplayer XOR Games. Commun. Math. Phys. 321, 181–207 (2013).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:65493
Deposited By: Tony Diaz
Deposited On:18 Mar 2016 22:51
Last Modified:10 Nov 2021 23:46

Repository Staff Only: item control page