Skip to main content
SpringerLink
Log in

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

  • Published:
Communications in Mathematical Physics Aims and scope Submit manuscript

Abstract

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 \({\sqrt{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 \({\sqrt{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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aspect A., Dalibard J., Roger G.: Experimental test of bell’s inequalities using time- varying analyzers. Phys. Rev. Lett. 49(25), 1804–1807 (1982)

    Article  MathSciNet  ADS  Google Scholar 

  2. Aspect A., Grangier P., Roger G.: Experimental tests of realistic local theories via bell’s theorem. Phys. Rev. Lett. 47(7), 460–463 (1981)

    Article  ADS  Google Scholar 

  3. Bell J.S.: On the Einstein–Podolsky– Rosen paradox. Physics 1, 195–200 (1964)

    Google Scholar 

  4. Braverman, M., Makarychev, K., Makarychev, Y., Naor, A.: The Grothendieck constant is strictly smaller than Krivine’s bound. In: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, Los Alamitos, CA: IEEE, 2011, pp. 453–462

  5. Buhrman, H., Regev, O., Scarpa, G., de Wolf, R.: Near-optimal and explicit Bell inequality violations. In: Proceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity, CCC ’11, Los Alamitos, CA: IEEE Computer Society, 2011, pp. 157–166

  6. Clauser J.F., Horne M.A., Shimony A., Holt R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880–884 (1969)

    Article  ADS  Google Scholar 

  7. Cleve, R., Høyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proceedings of the 19th IEEE Conference on Computational Complexity (CCC 2004), Los Alamitos, CA: IEEE, 2004, pp. 236–249

  8. Cooney, T., Junge, M., Palazuelos, C., Pérez-García, D.: Rank-one quantum games. Technical report http://arxiv.org/abs/1112.3563.2011v1 [quant-ph] 2011

  9. Einstein, A., Podolsky, P. Rosen, N.: Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47, 777–780 (1935)

    Google Scholar 

  10. Grothendieck, A.: Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. de Mat. São Paulo 81 (1953)

  11. Haagerup U.: A new upper bound for the complex grothendieck constant. Israel J.Mat. 60(2), 199–224 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  12. Haagerup U., Musat M.: On the best constants in noncommutative Khintchine-type inequalities. J. Funct. Anal. 250(2), 588–624 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hanson D.L., Wright F.T.: A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Stat. 3, 1079–1083 (1971)

    Article  MathSciNet  Google Scholar 

  14. Junge M., Palazuelos C.: Large violation of Bell inequalities with low entanglement. Commun. Math. Phys. 306(3), 695–746 (2011)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  15. Junge M., Palazuelos C., Pérez-García, D., Villanueva, I., Wolf, M.: Unbounded violations of bipartite Bell inequalities via operator space theory. Commun. Math. Phys. 300, 715–739 (2010)

    Google Scholar 

  16. Kempe J., Regev O., Toner B.: Unique games with entangled provers are easy. SIAM J. Comput. 39, 3207–3229 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  17. Latała R.: Estimates of moments and tails of gaussian chaoses. Ann. Prob. 34(6), 2315–2331 (2006)

    Article  MATH  Google Scholar 

  18. Loubenets, El.R.: Local quasi hidden variable modelling and violations of Bell-type inequalities by a multipartite quantum state. J. Math. Phys. 53(2), 022201 (2012)

    Google Scholar 

  19. Mermin N.D.: Extreme quantum entanglement in a superposition of macroscopically distinct states. Phys. Rev. Lett. 65(15), 1838–1840 (1990)

    Article  MathSciNet  ADS  MATH  Google Scholar 

  20. Nguyen, N.H., Drineas, P., Tran, T.D.: Tensor sparsification via a bound on the spectral norm of random tensors. Technical report http://arxiv.org/abs/1005.4732v1 [math.NA], 2010

  21. Palazuelos, C.: Personal communication. 2011

  22. Paulsen V.I.: Representations of function algebras, abstract operator spaces, and Banach space geometry. J. Funct. Anal 109(1), 113–129 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Pérez-García, D.,Wolf, M.M., Palazuelos, C., Villanueva, I., Junge,M.: Unbounded violation of tripartite Bell inequalities. Commun. Mathe. Phys. 279, 455 (2008)

    Article  ADS  MATH  Google Scholar 

  24. Pisier, G.: The volume of convex bodies and Banach space geometry. Cambridge: Cambridge University Press, 1999

  25. Pisier G.: Grothendieck’s theorem, past and present.. Bull. Amer. Math. Soc. 49, 267–323 (2012)

    Article  MathSciNet  Google Scholar 

  26. Pisier, G.: Tripartite Bell inequality, random matrices and trilinear forms. Technical report http://arxiv.org/abs/1203.2509v1 [math.OA], 2012

  27. Regev, O.: Bell violations through independent bases games. Technical report http://arxiv.org/abs/1101.1001.0576v3 [quant.ph], 2011

  28. Szarek, S.J.: Nets of Grassmann manifold and orthogonal group. In: Proceedings of Banach Spaces Workshop, A University of Iowa Press, 1982, pp. 169–185

  29. Tsirelson B.S.: Quantum analogues of the Bell inequalities, The case of two spatially separated domains. J. Soviet Math. 36, 557–570 (1987)

    Article  Google Scholar 

  30. Tsirelson, B.: Bell inequalities and operator algebras. http://www.math.tau.ac.il/~tsirel/download/beilopala.pdf

  31. Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Compressed sensing, Theory and Applications, Eldar, Y., Kutyniok, G., Cambridge: Cambridge Univ. Press, 2012 (Chapter)

  32. Zukowski M.: Bell theorem involving all settings of measuring apparatus. Phys. Lett. A. 177(4-5), 290–296 (1993)

    Article  MathSciNet  ADS  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CWI, Science Part 123, 1098 X6, Amsterdam, The Netherlands

    Jop Briët

  2. MIT CSAIL, 32 Vassar Street, Cambridge, MA, 02139, USA

    Thomas Vidick

Authors
  1. Jop Briët
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thomas Vidick
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Vidick.

Additional information

Communicated by M. B. Ruskai

Rights and permissions

Reprints and permissions

About this article

Cite this article

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). https://doi.org/10.1007/s00220-012-1642-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00220-012-1642-5

Keywords

Search

Navigation