Graph-Theoretic Approach to Quantum Correlations

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.

Figure 1

(a) Simplified representation of the exclusivity graph of the CHSH experiment ${\mathcal{G}}_{\mathrm{CHSH}}$. (b) Idem of the KCBS experiment, ${\mathcal{G}}_{\mathrm{KCBS}}$. Events are represented by vertices. Here, for simplicity, sets of pairwise exclusive events are represented by vertices in the same straight line or circumference rather than by cliques. (a) The exclusivity graph of $S_{\mathrm{CHSH}}$, denoted as $G_{\mathrm{CHSH}}$, is the induced subgraph of ${\mathcal{G}}_{\mathrm{CHSH}}$ obtained by removing all but the eight black vertices. An induced subgraph is obtained by selecting a subset of vertices and their incident edges. We use $G$ instead of ($G$, $w$) whenever vertex weights are all 1. $G_{\mathrm{CHSH}}$ is isomorphic to the eight-vertex circulant (1,4) graph $C{i}_8(1,4)$. (b) The exclusivity graph of $S_{\mathrm{KCBS}}$, denoted as $G_{\mathrm{KCBS}}$, is the induced subgraph of ${\mathcal{G}}_{\mathrm{KCBS}}$ obtained by removing all but the five black vertices. $G_{\mathrm{KCBS}}$ is isomorphic to a five-cycle $C_5$ (i.e., a pentagon).