A Caltech Library Service

Multiplayer XOR games and quantum communication complexity with clique-wise entanglement

Briët, Jop and Buhrman, Harry and Lee, Troy and Vidick, Thomas (2009) Multiplayer XOR games and quantum communication complexity with clique-wise entanglement. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


XOR games are a simple computational model with connections to many areas of complexity theory. Perhaps the earliest use of XOR games was in the study of quantum correlations. XOR games also have an interesting connection to Grothendieck's inequality, a fundamental theorem of analysis, which shows that two players sharing entanglement can achieve at most a constant factor advantage over players following classical strategies in an XOR game. Perez-Garcia et al. show that when the players share GHZ states, this advantage is bounded by a constant. We use a multilinear generalization of Grothendieck's inequality due to Blei and Tonge to simplify the proof of the second result and extend it to the case of so-called Schmidt states, answering an open problem of Perez-Garcia et al. Via a reduction given in that paper, this answers a 35-year-old problem in operator algebras due to Varopoulos, showing that the space of compact operators on a Hilbert space is a Q-algebra under Schur product. A further generalization of Grothendieck's inequality due to Carne lets us show that the gap between the entangled and classical value is at most a constant in any multiplayer XOR game in which the players are allowed to share combinations of GHZ states and EPR pairs of any dimension. As an application of our results, we show that the discrepancy method in communication complexity remains a lower bound in the multiparty model where the players have quantum communication and the kinds of entanglement discussed above. This answers an open question of Lee, Schechtman, and Shraibman.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:JB thanks Peter Høyer, TL thanks Gideon Schechtman, and TV thanks Falk Unger for useful discussions.
Record Number:CaltechAUTHORS:20190320-111726313
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93991
Deposited By: Tony Diaz
Deposited On:20 Mar 2019 18:29
Last Modified:03 Oct 2019 20:59

Repository Staff Only: item control page