Linear game non-contextuality and Bell inequalities—a graph-theoretic approach
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 ‘const...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2016-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/18/4/045020 |
| _version_ | 1797750965594488832 |
|---|---|
| author | M Rosicka R Ramanathan P Gnaciński K Horodecki M Horodecki P Horodecki S Severini |
| author_facet | M Rosicka R Ramanathan P Gnaciński K Horodecki M Horodecki P Horodecki S Severini |
| author_sort | M Rosicka |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T16:40:29Z |
| format | Article |
| id | doaj.art-66ab2e198eb24c7d9d29cea6e2fab1cd |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:40:29Z |
| publishDate | 2016-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-66ab2e198eb24c7d9d29cea6e2fab1cd2023-08-08T14:32:08ZengIOP PublishingNew Journal of Physics1367-26302016-01-0118404502010.1088/1367-2630/18/4/045020Linear game non-contextuality and Bell inequalities—a graph-theoretic approachM Rosicka0R Ramanathan1P Gnaciński2K Horodecki3M Horodecki4P Horodecki5S Severini6Faculty of Mathematics, Physics and Informatics, University of Gdańsk , 80-952 Gdańsk, Institute of Theoretical Physics and Astrophysics, and National Quantum Information Centre in Gdańsk, 81-824 Sopot, Poland; Faculty of Applied Physics and Mathematics, Gdańsk University of Technology , 80-233 Gdańsk, Poland and National Quantum Information Centre in Gdańsk, 81-824 Sopot, PolandFaculty of Mathematics, Physics and Informatics, University of Gdańsk , 80-952 Gdańsk, Institute of Theoretical Physics and Astrophysics, and National Quantum Information Centre in Gdańsk, 81-824 Sopot, PolandFaculty of Mathematics, Physics and Informatics, University of Gdańsk , 80-952 Gdańsk, Institute of Theoretical Physics and Astrophysics, and National Quantum Information Centre in Gdańsk, 81-824 Sopot, PolandFaculty of Mathematics, Physics and Informatics, University of Gdańsk , 80-952 Gdańsk, Institute of Informatics, and National Quantum Information Centre in Gdańsk, 81-824 Sopot, PolandFaculty of Mathematics, Physics and Informatics, University of Gdańsk , 80-952 Gdańsk, Institute of Theoretical Physics and Astrophysics, and National Quantum Information Centre in Gdańsk, 81-824 Sopot, PolandFaculty of Applied Physics and Mathematics, Gdańsk University of Technology , 80-233 Gdańsk, Poland and National Quantum Information Centre in Gdańsk, 81-824 Sopot, PolandDepartment of Computer Science and Department of Physics and Astronomy, University College London , WC1E 6BT London, UKWe 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.https://doi.org/10.1088/1367-2630/18/4/045020quantum non-localityquantum contextualitygraph theoryunique gamesquantum pseudo-telepathy |
| spellingShingle | M Rosicka R Ramanathan P Gnaciński K Horodecki M Horodecki P Horodecki S Severini Linear game non-contextuality and Bell inequalities—a graph-theoretic approach New Journal of Physics quantum non-locality quantum contextuality graph theory unique games quantum pseudo-telepathy |
| title | Linear game non-contextuality and Bell inequalities—a graph-theoretic approach |
| title_full | Linear game non-contextuality and Bell inequalities—a graph-theoretic approach |
| title_fullStr | Linear game non-contextuality and Bell inequalities—a graph-theoretic approach |
| title_full_unstemmed | Linear game non-contextuality and Bell inequalities—a graph-theoretic approach |
| title_short | Linear game non-contextuality and Bell inequalities—a graph-theoretic approach |
| title_sort | linear game non contextuality and bell inequalities a graph theoretic approach |
| topic | quantum non-locality quantum contextuality graph theory unique games quantum pseudo-telepathy |
| url | https://doi.org/10.1088/1367-2630/18/4/045020 |
| work_keys_str_mv | AT mrosicka lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach AT rramanathan lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach AT pgnacinski lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach AT khorodecki lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach AT mhorodecki lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach AT phorodecki lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach AT sseverini lineargamenoncontextualityandbellinequalitiesagraphtheoreticapproach |