ABSTRACT
n this work, we consider the following family of two prover one-round games. In the CHSH_q game, two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q without communicating with the other. The players' objective is to maximize the probability that their outputs satisfy a+b=xy in F_q. This game was introduced by Buhrman and Massar (PRA 2005) as a large alphabet generalization of the celebrated CHSH game---which is one of the most well-studied two-prover games in quantum information theory, and which has a large number of applications to quantum cryptography and quantum complexity.
Our main contributions in this paper are the first asymptotic and explicit bounds on the entangled and classical values of CHSH_q, and the realization of a rather surprising connection between CHSH_q and geometric incidence theory. On the way to these results, we also resolve a problem of Pawlowski and Winter about pairwise independent Information Causality, which, beside being interesting on its own, gives as an application a short proof of our upper bound for the entangled value of CHSH_q.
- J. S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1(3), 1964.Google Scholar
- M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the twentieth annual ACM symposium on Theory of computing(STOC), 1988. Google ScholarDigital Library
- J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1(01):1--32, 2005.Google ScholarCross Ref
- J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geometric & Functional Analysis, 14(1), 2004.Google Scholar
- J. Briët and T. Vidick. Explicit lower and upper bounds on the entangled value of multiplayer XOR games. Communications in Mathematical Physics, 321(1):181--207, 2013.Google ScholarCross Ref
- N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner. Bell nonlocality. quant-ph:1303.2849, 2013.Google Scholar
- H. Buhrman and S. Massar. Causality and Tsirel'son bounds. Physical Review A, 72(5), 052103, 2005.Google ScholarCross Ref
- H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf. Near-optimal and explicit Bell inequality violations. In IEEE 26th Annual Conference on Computational Complexity (CCC), pages 157--166, 2011. Google ScholarDigital Library
- J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880--884, 1969.Google ScholarCross Ref
- W. v. Dam. Implausible consequences of superstrong nonlocality. Natural Computing, 12(1), 2013. Google ScholarDigital Library
- I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC, pages 624--633, 2014. Google ScholarDigital Library
- A. K. Ekert. Quantum cryptography based on Bell's theorem. Physical Review Letters, 67(6):661--663, 1991.Google ScholarCross Ref
- N. Gisin. Bell inequalities: Many questions, a few answers. The Western Ontario Series in Philosophy of Science, 73, 2009.Google Scholar
- S.-W. Ji, J. Lee, J. Lim, K. Nagata, and H.-W. Lee. Multisetting Bell inequality for qudits. Physical Review A, 78(5):052103, 2008.Google ScholarCross Ref
- T. G. Jones. Explicit incidence bounds over general finite fields. arXiv preprint arXiv:1009.3899, 2010.Google Scholar
- T. G. Jones. New quantitative estimates on the incidence geometry and growth of finite sets. PhD Thesis, University of Bristol. arXiv:1301.4853, 2013.Google Scholar
- M. Junge and C. Palazuelos. Large violation of Bell inequalities with low entanglement. Communications in Mathematical Physics, 306(3):695--746, 2011.Google ScholarCross Ref
- R. Kasher and J. Kempe. Two-source extractors secure against quantum adversaries. Theory of Computing, 8(21), 2012.Google Scholar
- J. Kempe, O. Regev, and B. Toner. Unique games with entangled provers are easy. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2008. Google ScholarDigital Library
- Y.-C. Liang, C.-W. Lim, and D.-L. Deng. Reexamination of a multisetting Bell inequality for qudits. Physical Review A, 80(5), 2009.Google ScholarCross Ref
- N. Linden, S. Popescu, A. J. Short, and A. Winter. Quantum nonlocality and beyond: limits from nonlocal computation. Physical Review Letters, 99(18):180502, 2007.Google ScholarCross Ref
- M. Navascués, S. Pironio, and A. Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7), 2008.Google ScholarCross Ref
- M. Pawłowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. Zukowski. Information causality as a physical principle. Nature, 461, 2009.Google Scholar
- M. Pawłowski and A. Winter. Hyperbits: The information quasiparticles. Physical Review A, 85(2), 2012.Google ScholarCross Ref
- S. Popescu and D. Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379--385, 1994.Google ScholarCross Ref
- A. Rao. An exposition of Bourgain's 2-source extractor. Electronic Colloquium on Computational Complexity (ECCC), 14(034), 2007.Google Scholar
- R. Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771--777, 2011. Google ScholarDigital Library
- B. W. Reichardt, F. Unger, and U. Vazirani. A classical leash for a quantum system: command of quantum systems via rigidity oftextrmCHSH games. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science (ITCS), 2013. Google ScholarDigital Library
- E. Szemerédi and W. T. Trotter Jr. Extremal problems in discrete geometry. Combinatorica, 3(3--4):381--392, 1983.Google Scholar
- B. S. Tsirel'son. Quantum generalizations of Bell's inequality. Letters in Mathematical Physics, 4(2), 1980.Google Scholar
- B. S. Tsirel'son. Quantum analogues of the Bell inequalities. the case of two spatially separated domains. Journal of Soviet Mathematics, 36(4), 1987.Google ScholarCross Ref
- G. Wang. Functional boxes, communication complexity and information causality. arXiv preprint arXiv:1109.4988, 2011.Google Scholar
- R. F. Werner and M. M. Wolf. Bell inequalities and entanglement. Quantum Information and Computation (QIC), (3), 2001. Google ScholarDigital Library
Index Terms
- Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH
Recommendations
Characterizing multipartite entanglement by violation of CHSH inequalities
AbstractEntanglement of high-dimensional and multipartite quantum systems offer promising perspectives in quantum information processing. However, the characterization and measure of such kind of entanglement is of great challenge. Here, we consider the ...
Generalizations of the Szemerédi---Trotter Theorem
We generalize the Szemerédi---Trotter incidence theorem, to bound the number of complete flags in higher dimensions. Specifically, for each $$i=0,1,\ldots ,d-1$$i=0,1, ,d-1, we are given a finite set $$S_i$$Si of i-flats in $${\mathbb {R}}^d$$Rd or in $$...
Bound on genuine multipartite correlations from the principle of information causality
Quantum mechanics is not the unique no-signaling theory which is endowed with stronger-than-classical correlations, and there exists a broad class of no-signaling theories allowing even stronger-than-quantum correlations. The principle of information ...
Comments