Multipartite entanglement in XOR games

Open Access
Authors
Publication date 03-2013
Journal Quantum Information & Computation
Volume | Issue number 13 | 3&4
Pages (from-to) 334-360
Number of pages 27
Organisations
  • Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Abstract

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.

Document type Article
Language English
Published at https://doi.org/10.26421/QIC13.3-4
Published at http://www.rintonpress.com/xxqic13/qic-13-34/0334-0360.pdf
Other links https://www.scopus.com/pages/publications/84871707808
Downloads
0911.4007 (Submitted manuscript)
Permalink to this page
Back