Abstract
We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1 − o(1) fraction of all 2-player XOR games.
Supported by ESF project 2009/0216/1DP/1.1.1.2.0/09/APIA/VIAA/044 and FP7 FET-Open project QCS. Full version available as arXiv preprint arXiv:1112.3330.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Acin, A., Brunner, N., Gisin, N., Massar, S., Pironio, S., Scarani, V.: Device-independent security of quantum cryptography against collective attacks. Physical Review Letters 98, 230501 (2007)
Almeida, M.L., Bancal, J.-D., Brunner, N., Acin, A., Gisin, N., Pironio, S.: Guess your neighbour’s input: a multipartite non-local game with no quantum advantage. Physical Review Letters 104, 230404 (2010), also arXiv:1003.3844
Alon, N., Spencer, J.: The Probabilistic Method. Wiley (2000)
Bai, Z., Silverstein, J.: Spectral Analysis of Large Dimensional Random Matrices. Springer (2010)
Bennett, C.H., Brassard, G.: Quantum Cryptography: Public key distribution and coin tossing. In: Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, p. 175 (1984)
Braverman, M., Makarychev, K., Makarychev, Y., Naor, A.: The Groethendieck constant is strictly smaller than Krivine’s bound. In: Proceedings of FOCS 2011, pp. 453–462 (2011)
Briet, J., Vidick, T.: Explicit lower and upper bounds on the entangled value of multiplayer XOR games, arxiv: 1108.5647
Buhrman, H., Regev, O., Scarpa, G., de Wolf, R.: Near-optimal and explicit Bell inequality violations. In: Proceedings of Complexity 2011, pp. 157–166 (2011); also arxiv: 1012.5403
Cirel’son, B. (Tsirelson): Quantum generalizations of Bell’s inequality. Letters in Mathematical Physics 4, 93–100 (1980)
Clauser, J., Horne, M., Shimony, A., Holt, R.: Physical Review Letters 23, 880–884 (1969)
Cleve, R., Höyer, P., Toner, B., Watrous, J.: Consequences and limits of nonlocal strategies. In: Proceedings of CCC 2004, pp. 236–249 (2004); also quant-ph/0404076
Davidson, K., Szarek, S.: Local operator theory, random matrices and Banach spaces. In: Johnson, W.B., Lindenstrauss, J. (eds.) Handbook on the Geometry of Banach Spaces, vol. 1, pp. 317–366. Elsevier (2001)
Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics, 2nd edn. Addison-Wesley, Reading (1994)
Grothendieck, A.: Resume de la theorie metrique des produits tensoriels topologiques. Boletim Sociedade De Matematico de Sao Paulo 8, 1–79 (1953)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of STOC 1996, pp. 212–219 (1996)
Krivine, J.-L.: Sur la constante de Grothendieck. Comptes Rendus de l’Académie des Sciences, Series A-B 284, A445–A446 (1977)
Junge, M., Palazuelos, C.: Large violation of Bell inequalities with low entanglement. Communications in Mathematical Physics 306(3), 695–746 (2011); arXiv:1007.3043
Linial, N., Mendelson, S., Schechtman, G., Shraibman, A.: Complexity measures of sign matrices. Combinatorica 27(4), 439–463 (2007)
Marčenko, V.A., Pastur, L.A.: Distribution of eigenvalues for some sets of random matrices. Math. USSR Sbornik 1, 457–483 (1967)
Mitzenmacher, M., Upfal, E.: Probability and Computing. Randomized Algorithms and Their Analysis. Cambridge University Press (2005)
Montero, A.M., Tonge, A.M.: The Schur multiplication in tensor algebras. Studia Math. 68(1), 1–24 (1980)
Parisi, G.: The order parameter for spin glasses: a function on the interval 0-1. Journal of Physics A: Mathemathical and General 13, 1101–1112 (1980)
Reeds, J.A.: A new lower bound on the real Grothendieck constant (1991) (unpublished manuscript), http://www.dtc.umn.edu/reedsj/bound2.dvi
Sherrington, D., Kirkpatrick, S.: Infinite ranged models of spin glasses. Physical Review B 17, 4384–4403 (1978)
Shor, P.W.: Algorithms for quantum computation: Discrete logarithms and factoring. In: FOCS 1994, pp. 124–134. IEEE (1994)
Silman, J., Chailloux, A., Aharon, N., Kerenidis, I., Pironio, S., Massar, S.: Fully distrustful quantum cryptography. Physical Review Letters 106, 220501 (2011)
Simon, D.R.: On the power of quantum computation. In: FOCS 1994, pp. 116–123. IEEE (1994)
Stanley, R.: Enumerative Combinatorics, vol. 2. Cambridge University Press (1999)
Talagrand, M.: The generalized Parisi formula. Comptes Rendus de l’Académie des Sciences, Series I 337, 111–114 (2003)
Tao, T.: Topics in Random Matrix Theory, Draft of a book, http://terrytao.files.wordpress.com/2011/02/matrix-book.pdf
Wehner, S.: Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities. Physical Review A 73, 022110 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ambainis, A. et al. (2012). Quantum Strategies Are Better Than Classical in Almost Any XOR Game. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds) Automata, Languages, and Programming. ICALP 2012. Lecture Notes in Computer Science, vol 7391. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31594-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-31594-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31593-0
Online ISBN: 978-3-642-31594-7
eBook Packages: Computer ScienceComputer Science (R0)