Gnaciński, P;
Rosicka, M;
Ramanathan, R;
Horodecki, K;
Horodecki, M;
Horodecki, P;
Severini, S;
(2016)
Linear game non-contextuality and Bell inequalities - a graph-theoretic approach.
New Journal of Physics
, 18
, Article 045020. 10.1088/1367-2630/18/4/045020.
Text
njp_18_4_045020.pdf - Published Version Download (3MB) |
Abstract
We study the classical and quantum values of one- and two-party linear games, an important class of unique games that generalizes the well-known XOR games to the case of non-binary outcomes. We introduce a ``constraint graph" associated to such a game, with the constraints defining the linear 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 more general 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\'{a}sz theta number as a general upper bound on the quantum value even in the case of single-party contextual XOR-d games. Linear 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 linear 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.
Type: | Article |
---|---|
Title: | Linear game non-contextuality and Bell inequalities - a graph-theoretic approach |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1088/1367-2630/18/4/045020 |
Additional information: | Original content from this work may be used under the terms of the Creative Commons Attribution 3.0 licence. Any further distribution of this work must maintain attribution to the author(s) and the title of the work, journal citation and DOI. |
Keywords: | quant-ph, quant-ph |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
URI: | https://discovery.ucl.ac.uk/id/eprint/1495984 |
Archive Staff Only
View Item |