Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1401.7081 · Physical Review Letters

Graph-Theoretic Approach to Quantum Correlations

Adán Cabello, Simone Severini B, Andreas Winter

Published Jan 27, 2014• 359 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.112.040401

Related papers

Multigraph approach to quantum non-locality

Rafael Rabelo, Cristhiano Duarte, Antonio J López-Tarrida +2 more

Non-contextuality (NC) and Bell inequalities can be expressed as bounds $Ω$ for positive linear combinations $S$ of probabilities of events, $S \leq Ω$. 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 $I_3$, $I_{3322}$ 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.

arXiv:1407.5340•Journal of Physics A Mathematical and Theoretical•Oct 9, 2014•33 citations

(Non-)Contextuality of Physical Theories as an Axiom

Adán Cabello, Simone Severini B, Andreas Winter

We show that the noncontextual inequality proposed by Klyachko et al. [Phys. Rev. Lett. 101, 020403 (2008)] belongs to a broader family of inequalities, one associated to each compatibility structure of a set of events (a graph), and its independence number. These have the surprising property that the maximum quantum violation is given by the Lovasz theta-function of the graph, which was originally proposed as an upper bound on its Shannon capacity. Furthermore, probabilistic theories beyond quantum mechanics may have an even larger violation, which is given by the so-called fractional packing number. We discuss in detail, and compare, the sets of probability distributions attainable by noncontextual, quantum, and generalized models; the latter two are shown to have semidefinite and linear characterizations, respectively. The implications for Bell inequalities, which are examples of noncontextual inequalities, are discussed. In particular, we show that every Bell inequality can be recast as a noncontextual inequality a la Klyachko et al.

arXiv:1010.2163•Oct 11, 2010•196 citations

Exclusivity structures and graph representatives of local complementation orbits

Adán Cabello, Matthew G. Parker, Giannicola Scarpa +1 more

We describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovász number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the graph state associated with G, and exclusive events are adjacent. Mathematically, the graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. Finally, given the correspondence between graphs and exclusivity structures, we are able to compute the independence number for certain infinite families of graphs with the use of quantum non-locality, therefore highlighting an application of quantum theory in the proof of a purely combinatorial statement.

arXiv:1211.4250•Journal of Mathematical Physics•Jul 1, 2013•10 citations

Linear game non-contextuality and Bell inequalities—a graph-theoretic approach

Monika Rosicka, Ravishankar Ramanathan, P. Gnaciński +4 more

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.

arXiv:1511.05415•New Journal of Physics•Apr 21, 2016•10 citations

Combinatorial structures in quantum correlation: A new perspective

Rohit kumar, Satyabrata Adhikari

Graph-theoretic structures play a central role in the description and analysis of quantum systems. In this work, we introduce a new class of quantum states, called $A_α$-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix $D$ and the adjacency matrix $A_G$ of a graph $G$. The constructed states are different from the standard graph states arising from stabiliser formalism. Our approach is also different from the approach used by Braunstein et al. This class of states depend on a tunable mixing parameter $α\in (0,1]$. We first establish the conditions under which the associated operator $ρ_α^{A_G}$ is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for $A_α$-graph states in terms of graph parameters. This PPT condition involves only the Frobenius norm of the adjacency matrix of the graph, the degrees of the vertices and the total number of vertices. For simple graphs, we obtain the range of the parameter $α$ for which the $A_α$-graph states represent a class of entangled states. We then develop a graph-theoretic formulation of a moments-based entanglement detection criterion, focusing on the recently proposed $p_3$-PPT criterion, which relies on the second and third moments of the partial transposition. Since the estimation of these moments is experimentally accessible via randomised measurements, swap operations, and machine-learning-based protocols, our approach provides a physically relevant framework for detecting entanglement in structured quantum states derived from graphs. This work bridges graph theory and moments-based entanglement detection, offering a new perspective on the role of combinatorial structures in quantum correlations.

quant-pharXiv:2512.15686•Annals of Physics•Dec 18, 2025•0 citations

The Exclusivity Principle and the Set of Quantum Correlations

Bárbara Amaral

The most promising candidate for being the fundamental principle of quantum contextuality is the Exclusivity principle, which states that the sum of the probabilities of a set of pairwise exclusive events cannot exceed 1. By itself, the Exclusivity principle singles out the maximum quantum value for some important Bell and noncontextuality inequalities. We can get better results if we apply the E principle to more sophisticated scenarios. This happens because this principle exhibits activation effects: a distribution satisfying this principles does not necessarily satisfy it when combined with other distributions. Activation effects can be used to prove that the Exclusivity principle singles out the set of quantum distributions for the most simple noncontextuality inequality. It is still not known if the exclusivity principle solves the problem of explaining quantum contextuality completely, but many results have been proven that support the conjecture that it might. The main purpose of this thesis is to discuss in detail the situations in which the E principle can be used to rule out distributions outside the quantum set.

arXiv:1502.03235•Feb 11, 2015•6 citations
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.
Non-contextuality (NC) and Bell inequalities can be expressed as bounds ΩΩΩ for positive linear combinations SSS of probabilities of events, S≤ΩS \leq ΩS≤Ω. Exclusive events in SSS can be represented as adjacent vertices of a graph called the exclusivity graph of SSS. 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 SSS 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 NNN-partite Bell inequality, an edge-coloured multigraph composed of NNN 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 I3I_3I3​, I3322I_{3322}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.
We show that the noncontextual inequality proposed by Klyachko et al. [Phys. Rev. Lett. 101, 020403 (2008)] belongs to a broader family of inequalities, one associated to each compatibility structure of a set of events (a graph), and its independence number. These have the surprising property that the maximum quantum violation is given by the Lovasz theta-function of the graph, which was originally proposed as an upper bound on its Shannon capacity. Furthermore, probabilistic theories beyond quantum mechanics may have an even larger violation, which is given by the so-called fractional packing number. We discuss in detail, and compare, the sets of probability distributions attainable by noncontextual, quantum, and generalized models; the latter two are shown to have semidefinite and linear characterizations, respectively. The implications for Bell inequalities, which are examples of noncontextual inequalities, are discussed. In particular, we show that every Bell inequality can be recast as a noncontextual inequality a la Klyachko et al.
We describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovász number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the graph state associated with G, and exclusive events are adjacent. Mathematically, the graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. Finally, given the correspondence between graphs and exclusivity structures, we are able to compute the independence number for certain infinite families of graphs with the use of quantum non-locality, therefore highlighting an application of quantum theory in the proof of a purely combinatorial statement.
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.
Graph-theoretic structures play a central role in the description and analysis of quantum systems. In this work, we introduce a new class of quantum states, called AαA_αAα​-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix DDD and the adjacency matrix AGA_GAG​ of a graph GGG. The constructed states are different from the standard graph states arising from stabiliser formalism. Our approach is also different from the approach used by Braunstein et al. This class of states depend on a tunable mixing parameter α∈(0,1]α\in (0,1]α∈(0,1]. We first establish the conditions under which the associated operator ραAGρ_α^{A_G}ραAG​​ is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for AαA_αAα​-graph states in terms of graph parameters. This PPT condition involves only the Frobenius norm of the adjacency matrix of the graph, the degrees of the vertices and the total number of vertices. For simple graphs, we obtain the range of the parameter ααα for which the AαA_αAα​-graph states represent a class of entangled states. We then develop a graph-theoretic formulation of a moments-based entanglement detection criterion, focusing on the recently proposed p3p_3p3​-PPT criterion, which relies on the second and third moments of the partial transposition. Since the estimation of these moments is experimentally accessible via randomised measurements, swap operations, and machine-learning-based protocols, our approach provides a physically relevant framework for detecting entanglement in structured quantum states derived from graphs. This work bridges graph theory and moments-based entanglement detection, offering a new perspective on the role of combinatorial structures in quantum correlations.
The most promising candidate for being the fundamental principle of quantum contextuality is the Exclusivity principle, which states that the sum of the probabilities of a set of pairwise exclusive events cannot exceed 1. By itself, the Exclusivity principle singles out the maximum quantum value for some important Bell and noncontextuality inequalities. We can get better results if we apply the E principle to more sophisticated scenarios. This happens because this principle exhibits activation effects: a distribution satisfying this principles does not necessarily satisfy it when combined with other distributions. Activation effects can be used to prove that the Exclusivity principle singles out the set of quantum distributions for the most simple noncontextuality inequality. It is still not known if the exclusivity principle solves the problem of explaining quantum contextuality completely, but many results have been proven that support the conjecture that it might. The main purpose of this thesis is to discuss in detail the situations in which the E principle can be used to rule out distributions outside the quantum set.