A Caltech Library Service

Multipartite entanglement in XOR games

Briët, Jop and Buhrman, Harry and Lee, Troy and Vidick, Thomas (2013) Multipartite entanglement in XOR games. Quantum Information and Computation, 13 (3-4). pp. 334-360. ISSN 1533-7146.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We study multipartite entanglement in the context of XOR games. In particular, we study the ratio of the entangled and classical biases, which measure the maximum advantage of a quantum or classical strategy over a uniformly random strategy. For the case of two-player XOR games, Tsirelson proved that this ratio is upper bounded by the celebrated Grothendieck constant. In contrast, Pérez-García et al. proved the existence of entangled states that give quantum players an unbounded advantage over classical players in a three-player XOR game. We show that the multipartite entangled states that are most often seen in today’s literature can only lead to a bias that is a constant factor larger than the classical bias. These states include GHZ states, any state local-unitarily equivalent to combinations of GHZ and maximally entangled states shared between different subsets of the players (e.g., stabilizer states), as well as generalizations of GHZ states of the form ∑iɑi|i〉...|i〉 for arbitrary amplitudes ɑi. Our results have the following surprising consequence: classical three-player XOR games do not follow an XOR parallel repetition theorem, even a very weak one. Besides this, we discuss implications of our results for communication complexity and hardness of approximation. Our proofs are based on novel applications of extensions of Grothendieck’s inequality, due to Blei and Tonge, and Carne, generalizing Tsirelson’s use of Grothendieck’s inequality to bound the bias of two-player XOR games.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Alternate Title:Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
Additional Information:© 2013 Rinton Press. Received August 21, 2012. Revised November 26, 2012. Communicated by: R Cleve & A Harrow. JB thanks Carlos González Guillén for providing reference [58], Peter Høyer for useful discussions and Monique Laurent for helpful comments on an earlier version of this manuscript. TL thanks Gideon Schechtman, and TV thanks Falk Unger for useful discussions. JB and HB were supported by the EU grant QCS.
Funding AgencyGrant Number
European Research Council (ERC)UNSPECIFIED
Subject Keywords:Entanglement, XOR games, Grothendieck’s inequality, parallel repetition, communication complexity
Issue or Number:3-4
Record Number:CaltechAUTHORS:20140909-144447941
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49503
Deposited By: Ruth Sustaita
Deposited On:10 Sep 2014 20:14
Last Modified:03 Oct 2019 07:14

Repository Staff Only: item control page