Non-contextuality (NC) and Bell inequalities can be expressed as bounds Ω for positive linear combinations S of probabilities of events, S≤Ω. Exclusive events in S can be represented as adjacent vertices of a graph called the exclusivity graph of S. In the case that events correspond to the outcomes of quantum projective measurements, quantum probabilities are intimately related to the Grötschel-Lovász-Schrijver theta body of the exclusivity graph. Then, one can easily compute an upper bound to the maximum quantum violation of any NC or Bell inequality by optimizing S over the theta body and calculating the Lovász number of the corresponding exclusivity graph. In some cases, this upper bound is tight and gives the exact maximum quantum violation. However, in general, this is not the case. The reason is that the exclusivity graph does not distinguish among the different ways exclusivity can occur in Bell-inequality (and similar) scenarios. An interesting question is whether there is a graph-theoretical concept which accounts for this problem. Here we show that, for any given N-partite Bell inequality, an edge-coloured multigraph composed of N single-colour graphs can be used to encode the relationships of exclusivity between each party's parts of the events. Then, the maximum quantum violation of the Bell inequality is exactly given by a refinement of the Lovász number that applies to these edge-coloured multigraphs. We show how to calculate upper bounds for this number using a hierarchy of semi-definite programs and calculate upper bounds for I3, I3322 and the three bipartite Bell inequalities whose exclusivity graph is a pentagon. The multigraph-theoretical approach introduced here may remove some obstacles in the program of explaining quantum correlations from first principles.
Non-contextuality (NC) and Bell inequalities can be expressed as bounds Ω for positive linear combinations S of probabilities of events, S≤Ω. Exclusive events in S can be represented as adjacent vertices of a graph called the exclusivity graph of S. In the case that events correspond to the outcomes of quantum projective measurements, quantum probabilities are intimately related to the Grötschel-Lovász-Schrijver theta body of the exclusivity graph. Then, one can easily compute an upper bound to the maximum quantum violation of any NC or Bell inequality by optimizing S over the theta body and calculating the Lovász number of the corresponding exclusivity graph. In some cases, this upper bound is tight and gives the exact maximum quantum violation. However, in general, this is not the case. The reason is that the exclusivity graph does not distinguish among the different ways exclusivity can occur in Bell-inequality (and similar) scenarios. An interesting question is whether there is a graph-theoretical concept which accounts for this problem. Here we show that, for any given N-partite Bell inequality, an edge-coloured multigraph composed of N single-colour graphs can be used to encode the relationships of exclusivity between each party's parts of the events. Then, the maximum quantum violation of the Bell inequality is exactly given by a refinement of the Lovász number that applies to these edge-coloured multigraphs. We show how to calculate upper bounds for this number using a hierarchy of semi-definite programs and calculate upper bounds for I3, I3322 and the three bipartite Bell inequalities whose exclusivity graph is a pentagon. The multigraph-theoretical approach introduced here may remove some obstacles in the program of explaining quantum correlations from first principles.
Non-contextuality (NC) and Bell inequalities can be expressed as bounds Ω for positive linear combinations S of probabilities of events, S≤Ω. Exclusive events in S can be represented as adjacent vertices of a graph called the exclusivity graph of S. In the case that events correspond to the outcomes of quantum projective measurements, quantum probabilities are intimately related to the Grötschel-Lovász-Schrijver theta body of the exclusivity graph. Then, one can easily compute an upper bound to the maximum quantum violation of any NC or Bell inequality by optimizing S over the theta body and calculating the Lovász number of the corresponding exclusivity graph. In some cases, this upper bound is tight and gives the exact maximum quantum violation. However, in general, this is not the case. The reason is that the exclusivity graph does not distinguish among the different ways exclusivity can occur in Bell-inequality (and similar) scenarios. An interesting question is whether there is a graph-theoretical concept which accounts for this problem. Here we show that, for any given N-partite Bell inequality, an edge-coloured multigraph composed of N single-colour graphs can be used to encode the relationships of exclusivity between each party's parts of the events. Then, the maximum quantum violation of the Bell inequality is exactly given by a refinement of the Lovász number that applies to these edge-coloured multigraphs. We show how to calculate upper bounds for this number using a hierarchy of semi-definite programs and calculate upper bounds for I3, I3322 and the three bipartite Bell inequalities whose exclusivity graph is a pentagon. The multigraph-theoretical approach introduced here may remove some obstacles in the program of explaining quantum correlations from first principles.
Correlations in Bell and noncontextuality inequalities can be expressed as a positive linear combination of probabilities of events. Exclusive events can be represented as adjacent vertices of a graph, so correlations can be associated to a subgraph. We show that the maximum value of the correlations for classical, quantum, and more general theories is the independence number, the Lovász number, and the fractional packing number of this subgraph, respectively. We also show that, for any graph, there is always a correlation experiment such that the set of quantum probabilities is exactly the Grötschel-Lovász-Schrijver theta body. This identifies these combinatorial notions as fundamental physical objects and provides a method for singling out experiments with quantum correlations on demand.
The Clauser-Horne-Shimony-Holt (CHSH) inequalities are the most famous examples of Bell inequalities. Cabello, Severini, and Winter came up with a graph approach to noncontextuality inequalities, which connects some graph-theoretic concepts to quantum and classical correlations. For example, the theta body of the exclusivity graph can be associated with the set of correlations achieved by quantum theory. Following the Cabello-Severini-Winter (CSW) approach, one may think that the theta body of the CHSH graph TH(GCHSH) is equal to the quantum set of the CHSH Bell inequality QCHSH, but is this really true? All assumptions about the CHSH inequalities come from Bell scenarios, while the CSW approach only demands the exclusivity structure of a noncontextuality (NC) scenario. To deal with the extra structure related to the presence of different players in a Bell scenario like the CHSH one, the colored-graph approach was introduced. Does it make any difference to think about the CHSH scenario as a Bell one or a more general NC scenario? The Bell CHSH inequality is represented by a bicolored graph G and the NC CHSH inequality by a simple graph G, which is the shadow of the colored graph G. In general, we have that the theta body of the colored graph ${\ensuremath{\theta}}_{c}(\mathcal{G})$ is a subset of the theta body of its shadow graph TH(G) in the same way that the Lov\'asz number, which corresponds to the quantum bound, of the simple graph $\ensuremath{\vartheta}(G)$ is greater than or equal to the Lov\'asz number of the colored graph ${\ensuremath{\vartheta}}_{c}(\mathcal{G})$. In the case of the CHSH inequality, we have that $\ensuremath{\vartheta}(G)={\ensuremath{\vartheta}}_{c}(\mathcal{G})$. Does this accident also hold for the corresponding quantum sets? Is it true that $\mathrm{TH}(G)={\ensuremath{\theta}}_{c}(\mathcal{G})$, which would mean that every correlation reached by quantum theory applied to the CHSH NC scenario could also be obtained at the in principle more restrictive CHSH Bell scenario? In this paper our answer to such a question is negative. We show that ${\ensuremath{\theta}}_{c}(\mathcal{G})\ensuremath{\nsubseteq}\mathrm{TH}(G)$ and therefore that there are quantum correlations which cannot be obtained under Bell restrictions.
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á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.
It is well known that certain measurement scenarios behave in a way which can not be explained by classical theories but by quantum theories. This behaviours are usually studied by Bell or non-contextuality (NC) inequalities. Knowing the maximal classical and quantum bounds of this inequalities is interesting, but tells us little about the quantum set Q of all quantum behaviours P. Despite having a constructive description of the quantum set associated to a given inequality, the freedom to choose quantum dimension, quantum states, and quantum measurements makes the shape of such convex bodies quite elusive. It is well known that a NC-inequality can be associated to a graph and the quantum set is a combinatorial object. Extra conditions, like Bell concept of parts, may restrict the behaviours achievable within quantum theory for a given scenario. For the simplest case, CHSH inequality, the NC and Bell versions share the same quantum bound. By exploring a family of intermediate coloured graphs, we show that CHSH NC quantum set is strictly larger than CHSH Bell quantum set. In graph language, the coloured-THETA body of the coloured CHSH graph is a proper subset of the THETA body of its shadow graph.
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.