×

Linear game non-contextuality and Bell inequalities – a graph-theoretic approach. (English) Zbl 1456.81019

Summary: We study the classical and quantum values of a class of one- and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR (XOR-d) games we study are a subclass of the well-known linear games. We introduce a ‘constraint graph’ associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the graph-theoretic characterization to relate the task of finding equivalent games to the notion of signed graphs and switching equivalence from graph theory. We relate the problem of computing the classical value of single-party anti-correlation XOR games to finding the edge bipartization number of a graph, which is known to be MaxSNP hard, and connect the computation of the classical value of XOR-d games to the identification of specific cycles in the graph. We construct an orthogonality graph of the game from the constraint graph and study its Lov?sz theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. XOR-d games possess appealing properties for use in device-independent applications such as randomness of the local correlated outcomes in the optimal quantum strategy. We study the possibility of obtaining quantum algebraic violation of these games, and show that no finite XOR-d game possesses the property of pseudo-telepathy leaving the frequently used chained Bell inequalities as the natural candidates for such applications. We also show this lack of pseudo-telepathy for multi-party XOR-type inequalities involving two-body correlation functions.

MSC:

81P13 Contextuality in quantum theory
81P15 Quantum measurement theory, state operations, state preparations
91A05 2-person games
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bell J S 1964 Physics1 195 · doi:10.1103/PhysicsPhysiqueFizika.1.195
[2] Grudka A, Horodecki K, Horodecki M, Horodecki P, Horodecki R, Joshi P, Kłobus W and Wojcik A 2014 Phys. Rev. Lett.112 120401 · doi:10.1103/PhysRevLett.112.120401
[3] Collins D, Gisin N, Linden N, Massar S and Popescu S 2002 Phys. Rev. Lett.88 040404 · Zbl 1243.81029 · doi:10.1103/PhysRevLett.88.040404
[4] Buhrman H, Cleve R, Massar S and de Wolf R 2010 Rev. Mod. Phys.82 665 · doi:10.1103/RevModPhys.82.665
[5] Klyachko A A, Can M A, Binicioglu S and Shumovsky A S 2008 Phys. Rev. Lett.101 020403 · Zbl 1228.81068 · doi:10.1103/PhysRevLett.101.020403
[6] Lanyon B P, Barbieri M, Almeida M P, Jennewein T, Ralph T C, Resch K J, Pryde G J, O’Brien J L, Gilchrist A and White A G 2009 Nat. Phys.5 134 · doi:10.1038/nphys1150
[7] Ralph T C, Resch K J and Gilchrist A 2007 Phys. Rev. A 75 022313 · doi:10.1103/PhysRevA.75.022313
[8] Etcheverry S, Cañas G, Gómez E S, Nogueira W A T, Saavedra C, Xavier G B and Lima G 2013 Sci. Rep.3 2316 · doi:10.1038/srep02316
[9] Arora S, Lund C, Motwani R, Sudan M and Szegedy M 1998 J. ACM45 501 · Zbl 1065.68570 · doi:10.1145/278298.278306
[10] Arora S and Safram S 1998 J. ACM45 70 · Zbl 0903.68076 · doi:10.1145/273865.273901
[11] Raz R 1998 SIAM J. Comput.27 763 · Zbl 0911.68082 · doi:10.1137/S0097539795280895
[12] Hastad J 2001 J. ACM48 798 · Zbl 1127.68405 · doi:10.1145/502090.502098
[13] Khot S 2002 Proc. 34th ACM Symp. on Theory of Computingvol 3 p 767
[14] Navascués M, Pironio S and Acín A 2008 New J. Phys.10 073013 · doi:10.1088/1367-2630/10/7/073013
[15] Ramanathan R, Soeda A, Kurzynski P and Kaszlikowski D 2012 Phys. Rev. Lett.109 050404 · doi:10.1103/PhysRevLett.109.050404
[16] Brunner N, Cavalacanti D, Pironio S, Scarani V and Wehner S 2014 Rev. Mod. Phys.86 419 · doi:10.1103/RevModPhys.86.419
[17] Kempe J, Regev O and Toner B 2010 SIAM J. Comput.39 3207 · Zbl 1244.68040 · doi:10.1137/090772885
[18] Cabello A 2008 Phys. Rev. Lett.101 210401 · doi:10.1103/PhysRevLett.101.210401
[19] Cabello A, Severini S and Winter A 2014 Phys. Rev. Lett.112 040401 · doi:10.1103/PhysRevLett.112.040401
[20] Cleve R, Hoyer P, Toner B and Watrous J 2004 Proc. 19th IEEE Annual Conf. on Computational Complexity p 236
[21] Papadimitriou C H and Yannakakis M 1991 J. Comput. Syst. Sci.43 425 · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X
[22] Agarwal A, Charikar M, Makarychev K and Makarychev Y 2005 Proc. 37th STOC (New York: ACM) p 573
[23] Acín A, Fritz T, Leverrier A and Sainz A B 2015 Commun. Math. Phys.334 533 · Zbl 1312.81010 · doi:10.1007/s00220-014-2260-1
[24] Lovász L 1979 IEEE Transactions on Information Theory25 1-7 · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[25] Rosicka M and Severini S in preparation
[26] Tsirel’son B S 1987 J. Sov. Math.36 557 · Zbl 0617.46066 · doi:10.1007/BF01663472
[27] Zukowski M, Zeilinger A and Horne M 1997 Phys. Rev. A 55 2564 · doi:10.1103/PhysRevA.55.2564
[28] Barrett J, Hardy L and Kent A 2005 Phys. Rev. Lett.95 010503 · doi:10.1103/PhysRevLett.95.010503
[29] Miller C A and Shi Y 2014 Proc. 46th Annual ACM STOC 417-26 · Zbl 1315.94094 · doi:10.1145/2591796.2591843
[30] Colbeck R and Renner R 2012 Nat. Phys.8 450 · doi:10.1038/nphys2300
[31] Barrett J, Kent A and Pironio S 2006 Phys. Rev. Lett.97 170409 · doi:10.1103/PhysRevLett.97.170409
[32] Brandão F G S L, Ramanathan R, Horodecki K, Horodecki M, Horodecki P, Wojewódka H and Szarek T 2013 arXiv:1308.4635
[33] Gallego R, Masanes L, de la Torre G, Dhara C, Aolita L and Acín A 2013 Nat. Commun.4 2654 · doi:10.1038/ncomms3654
[34] Liang Y-C, Lim C-W and Deng D-L 2009 Phys. Rev. A 80 052116 · doi:10.1103/PhysRevA.80.052116
[35] Tura J, Augusiak R, Sainz A B, Vértesi T, Lewenstein M and Acín A 2014 Science344 1256 · Zbl 1355.81192 · doi:10.1126/science.1247715
[36] Mermin N D 1990 Phys. Rev. Lett.65 1838 · Zbl 0971.81507 · doi:10.1103/PhysRevLett.65.1838
[37] Ekert A K 1991 Phys. Rev. Lett.67 661 · Zbl 0990.94509 · doi:10.1103/PhysRevLett.67.661
[38] Kochen S and Specker E P 1967 J. Math. Mech.17 59 · Zbl 0156.23302
[39] Howard M, Wallman J J, Veitch V and Emerson J 2014 Nature510 351 · doi:10.1038/nature13460
[40] Delfosse N, Guerin P A, Bian J and Raussendorf R 2015 Phys. Rev. X 5 021003 · doi:10.1103/PhysRevX.5.021003
[41] Vazirani U and Vidick T 2014 Phys. Rev. Lett.113 140501 · doi:10.1103/PhysRevLett.113.140501
[42] Bavarian M and Shor P W 2015 Proc. 2015 Conf. on Innovations in Theoretical Computer Science ITCS 213
[43] Bavarian M and Shor P W 2013 arXiv:1311.5186
[44] Pivoluska M and Plesch M 2016 New J. Phys.18 025013 · Zbl 1456.91003
[45] Buhrman H and Massar S 2005 Phys. Rev. A 72 052103 · doi:10.1103/PhysRevA.72.052103
[46] Ramanathan R, Augusiak R and Murta G 2016 Phys. Rev. A 93 022333 · doi:10.1103/PhysRevA.93.022333
[47] Murta G, Ramanathan R, Móller N and Cunha M T 2016 Phys. Rev. A 93 022305 · doi:10.1103/PhysRevA.93.022305
[48] Trevisan L 2008 Theory Comput.4 111 · Zbl 1213.68320 · doi:10.4086/toc.2008.v004a005
[49] Clauser J F, Horne M A, Shimony A and Holt R A 1969 Phys. Rev. Lett.23 880 · Zbl 1371.81014 · doi:10.1103/PhysRevLett.23.880
[50] Popescu S and Rohrlich D 1994 Found. Phys.24 379 · doi:10.1007/BF02058098
[51] Braunstein S L and Caves C M 1988 Phys. Rev. Lett.61 662 · doi:10.1103/PhysRevLett.61.662
[52] Araújo M, Quintino M T, Budroni C, Cunha M T and Cabello A 2013 Phys. Rev. A 88 022118 · doi:10.1103/PhysRevA.88.022118
[53] Harary F 1953 Michigan Math. J.2 143-6 · Zbl 0056.42103 · doi:10.1307/mmj/1028989917
[54] Roberts F S 1978 Graph Theory and its Applications to Problems of Society (Philadelphia: SIAM) · Zbl 0452.05001 · doi:10.1137/1.9781611970401
[55] Zaslavsky T 1998 Electronic J. Combin.8 and 1999 Dynamic Surveys No. DS8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.