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.
Similar content being viewed by others
References
Aspect A., Dalibard J., Roger G.: Experimental test of bell’s inequalities using time- varying analyzers. Phys. Rev. Lett. 49(25), 1804–1807 (1982)
Aspect A., Grangier P., Roger G.: Experimental tests of realistic local theories via bell’s theorem. Phys. Rev. Lett. 47(7), 460–463 (1981)
Bell J.S.: On the Einstein–Podolsky– Rosen paradox. Physics 1, 195–200 (1964)
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
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
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)
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
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
Einstein, A., Podolsky, P. Rosen, N.: Can quantum-mechanical description of physical reality be considered complete? Phys. Rev. 47, 777–780 (1935)
Grothendieck, A.: Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. de Mat. São Paulo 81 (1953)
Haagerup U.: A new upper bound for the complex grothendieck constant. Israel J.Mat. 60(2), 199–224 (1987)
Haagerup U., Musat M.: On the best constants in noncommutative Khintchine-type inequalities. J. Funct. Anal. 250(2), 588–624 (2007)
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)
Junge M., Palazuelos C.: Large violation of Bell inequalities with low entanglement. Commun. Math. Phys. 306(3), 695–746 (2011)
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)
Kempe J., Regev O., Toner B.: Unique games with entangled provers are easy. SIAM J. Comput. 39, 3207–3229 (2010)
Latała R.: Estimates of moments and tails of gaussian chaoses. Ann. Prob. 34(6), 2315–2331 (2006)
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)
Mermin N.D.: Extreme quantum entanglement in a superposition of macroscopically distinct states. Phys. Rev. Lett. 65(15), 1838–1840 (1990)
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
Palazuelos, C.: Personal communication. 2011
Paulsen V.I.: Representations of function algebras, abstract operator spaces, and Banach space geometry. J. Funct. Anal 109(1), 113–129 (1992)
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)
Pisier, G.: The volume of convex bodies and Banach space geometry. Cambridge: Cambridge University Press, 1999
Pisier G.: Grothendieck’s theorem, past and present.. Bull. Amer. Math. Soc. 49, 267–323 (2012)
Pisier, G.: Tripartite Bell inequality, random matrices and trilinear forms. Technical report http://arxiv.org/abs/1203.2509v1 [math.OA], 2012
Regev, O.: Bell violations through independent bases games. Technical report http://arxiv.org/abs/1101.1001.0576v3 [quant.ph], 2011
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
Tsirelson B.S.: Quantum analogues of the Bell inequalities, The case of two spatially separated domains. J. Soviet Math. 36, 557–570 (1987)
Tsirelson, B.: Bell inequalities and operator algebras. http://www.math.tau.ac.il/~tsirel/download/beilopala.pdf
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)
Zukowski M.: Bell theorem involving all settings of measuring apparatus. Phys. Lett. A. 177(4-5), 290–296 (1993)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by M. B. Ruskai
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00220-012-1642-5