LIPIcs.TQC.2019.4.pdf
- Filesize: 1.96 MB
- 17 pages
Document
The RGB No-Signalling Game
Authors
-
Part of:
Volume:
14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-05-31
File
Document Identifiers
Acknowledgements
We thank Gilles Brassard, Arne Hansen, Adel Magra, Alberto Montina, Louis Salvail, Stefan Wolf and Nan Yang for discussions about early versions of this work.
Cite As Get BibTex
Xavier Coiteux-Roy and Claude Crépeau. The RGB No-Signalling Game. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.TQC.2019.4
Abstract
Introducing the simplest of all No-Signalling Games: the RGB Game where two verifiers interrogate two provers, Alice and Bob, far enough from each other that communication between them is too slow to be possible. Each prover may be independently queried one of three possible colours: Red, Green or Blue. Let a be the colour announced to Alice and b be announced to Bob. To win the game they must reply colours x (resp. y) such that a != x != y != b. This work focuses on this new game mainly as a pedagogical tool for its simplicity but also because it triggered us to introduce a new set of definitions for reductions among multi-party probability distributions and related non-locality classes. We show that a particular winning strategy for the RGB Game is equivalent to the PR-Box of Popescu-Rohrlich and thus No-Signalling. Moreover, we use this example to define No-Signalling in a new useful way, as the intersection of two natural classes of multi-party probability distributions called one-way signalling. We exhibit a quantum strategy able to beat the classical local maximum winning probability of 8/9 shifting it up to 11/12. Optimality of this quantum strategy is demonstrated using the standard tool of semidefinite programming.
Subject Classification
ACM Subject Classification
- Theory of computation → Quantum information theory
Keywords
- No-Signalling
- Quantum Entanglement
- Non-Locality
- Bell inequality
- Semidefinite Programming
- Non-locality Hierarchy
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Antonio Acín, Tobias Fritz, Anthony Leverrier, and Ana Belén Sainz. A Combinatorial Approach to Nonlocality and Contextuality. Communications in Mathematical Physics, 334(2):533-628, March 2015. URL: http://dx.doi.org/10.1007/s00220-014-2260-1.
- Howard Barnum, Christopher A. Fuchs, Joseph M. Renes, and Alexander Wilce. Influence-free states on compound quantum systems. CoRR, quant-ph/0507108v1, 2005. URL: http://arxiv.org/abs/1504.00943.
- Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, and David Roberts. Nonlocal correlations as an information-theoretic resource. Phys. Rev. A, 71:022101, February 2005. URL: http://dx.doi.org/10.1103/PhysRevA.71.022101.
-
John S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1:195-200, 1964.
- Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover Interactive Proofs: How to Remove Intractability Assumptions. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, pages 113-131, New York, NY, USA, 1988. ACM. URL: http://dx.doi.org/10.1145/62212.62223.
-
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
- B.S. Cirel’son. Quantum generalizations of Bell’s inequality. Lett Math Phys, 4(93), 1980. URL: http://dx.doi.org/10.1007/BF00417500.
- Frédéric Dupuis, Nicolas Gisin, Avinatan Hassidim, André Allan Méthot, and Haran Pilpel. No nonlocal box is universal. Journal of Mathematical Physics, 48(8):082107, 2007. URL: http://dx.doi.org/10.1063/1.2767538.
- Manuel Forster and Stefan Wolf. Bipartite units of nonlocality. Phys. Rev. A, 84:042112, October 2011. URL: http://dx.doi.org/10.1103/PhysRevA.84.042112.
- Jon Hudson. Could someone explain quantum entanglement to me like I'm 5 years old (in Reply to). https://www.quora.com/Could-someone-explain-quantum-entanglement-to-me-like-Im-5-years-old, QUORA, May 2018.
- Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew Chi-Chih Yao. Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA, pages 187-198. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/CCC.2008.12.
- N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65:3373-3376, December 1990. URL: http://dx.doi.org/10.1103/PhysRevLett.65.3373.
- Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151(3):107-108, 1990. URL: http://dx.doi.org/10.1016/0375-9601(90)90172-K.
- Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379-385, 1994. URL: http://dx.doi.org/10.1007/BF02058098.
-
Stephanie Wehner. Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities. Physical Review A, 73(2):022110, 2006.