Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Multipartite entanglement in XOR games
 
research article

Multipartite entanglement in XOR games

Briët, Jop
•
Buhrman, Harry
•
Lee, Troy
Show more
March 1, 2013
Quantum Information & Computation

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, Pe ́rez-Garci{dotless} ́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 formPi 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.

  • Details
  • Metrics
Type
research article
DOI
10.26421/QIC13.3-4-11
Scopus ID

2-s2.0-84871707808

Author(s)
Briët, Jop

Centrum Wiskunde & Informatica

Buhrman, Harry

Universiteit van Amsterdam

Lee, Troy

National University of Singapore

Vidick, Thomas  orcid-logo

Massachusetts Institute of Technology

Date Issued

2013-03-01

Publisher

Rinton Press

Published in
Quantum Information & Computation
Volume

13

Issue

3-4

Start page

0334

End page

0360

Subjects

Communication complexity

•

Entanglement

•

Grothendieck's inequality

•

Parallel repetition

•

XOR games

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Available on Infoscience
November 25, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256301
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés