File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Linear game non-contextuality and Bell inequalities - A graph-theoretic approach

TitleLinear game non-contextuality and Bell inequalities - A graph-theoretic approach
Authors
Keywordsquantum pseudo-telepathy
graph theory
quantum contextuality
quantum non-locality
unique games
Issue Date2016
Citation
New Journal of Physics, 2016, v. 18, n. 4, article no. 045020 How to Cite?
Abstract© 2016 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. 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.
Persistent Identifierhttp://hdl.handle.net/10722/277042
ISSN
2017 Impact Factor: 3.579
2015 SCImago Journal Rankings: 1.902

 

DC FieldValueLanguage
dc.contributor.authorRosicka, M.-
dc.contributor.authorRamanathan, R.-
dc.contributor.authorGnaciński, P.-
dc.contributor.authorHorodecki, K.-
dc.contributor.authorHorodecki, M.-
dc.contributor.authorHorodecki, P.-
dc.contributor.authorSeverini, S.-
dc.date.accessioned2019-09-18T08:35:25Z-
dc.date.available2019-09-18T08:35:25Z-
dc.date.issued2016-
dc.identifier.citationNew Journal of Physics, 2016, v. 18, n. 4, article no. 045020-
dc.identifier.issn1367-2630-
dc.identifier.urihttp://hdl.handle.net/10722/277042-
dc.description.abstract© 2016 IOP Publishing Ltd and Deutsche Physikalische Gesellschaft. 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.-
dc.languageeng-
dc.relation.ispartofNew Journal of Physics-
dc.rightsThis work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.-
dc.subjectquantum pseudo-telepathy-
dc.subjectgraph theory-
dc.subjectquantum contextuality-
dc.subjectquantum non-locality-
dc.subjectunique games-
dc.titleLinear game non-contextuality and Bell inequalities - A graph-theoretic approach-
dc.typeArticle-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1088/1367-2630/18/4/045020-
dc.identifier.scopuseid_2-s2.0-84996532491-
dc.identifier.volume18-
dc.identifier.issue4-
dc.identifier.spagearticle no. 045020-
dc.identifier.epagearticle no. 045020-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats