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:1407.5340 · Journal of Physics A Mathematical and Theoretical

Multigraph approach to quantum non-locality

Rafael Rabelo, Cristhiano Duarte, Antonio J López-Tarrida, Marcelo Terra Cunha, Adán Cabello

Published Oct 9, 2014• 33 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/1751-8113/47/42/424021

Related papers

Graph-Theoretic Approach to Quantum Correlations

Adán Cabello, Simone Severini B, Andreas Winter

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.

arXiv:1401.7081•Physical Review Letters•Jan 27, 2014•359 citations

Quantum sets of the multicolored-graph approach to contextuality

Lina Vandré, Marcelo Terra Cunha

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 $\mathrm{TH}({G}_{\text{CHSH}})$ is equal to the quantum set of the CHSH Bell inequality ${\mathcal{Q}}_{\text{CHSH}}$, 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 $\mathcal{G}$ and the NC CHSH inequality by a simple graph $G$, which is the shadow of the colored graph $\mathcal{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 $\mathrm{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.

arXiv:2105.08561•Physical Review A•Dec 16, 2022•7 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

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

Experimental observation of quantum contextuality beyond Bell nonlocality

Zhenghao Liu, Hui-Xian Meng, Zhen‐Peng Xu +10 more

Bell nonlocality and quantum contextuality are two important resources which, however, behave very differently in many tasks where the quantum correlation has an edge over its classical counterpart. In this work, we directly compare these two behaviors, which via the Cabello-Severini-Winter graph-theoretical approach, can be associated with a same exclusivity graph. In particular, we consider the exclusivity graph that leads to ${I}_{3322}$-type inequalities in the Bell and the contextual scenarios, respectively. We find that maximal violation of Bell inequality is around 6.251, and maximal violation of the noncontextuality inequality is around 6.588 for a five-dimensional system and 6.571 for a four-dimensional system, respectively. The results predict a gap of $\mathrm{\ensuremath{\Delta}}\ensuremath{\approx}0.32$ between quantum contextuality and Bell nonlocality. We then present an experimental observation of the gap by employing both the maximally entangled photon pairs from the spontaneous parametric down-conversion process and the single photons encoded into qudits from an intrinsic defect in gallium nitride. Our results will further deepen the understanding of different types of quantum correlations.

Physical Review A•Oct 22, 2019•4 citations

Basic exclusivity graphs in quantum correlations

Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida +1 more

A fundamental problem is to understand why quantum theory only violates some noncontextuality (NC) inequalities and identify the physical principles that prevent higher-than-quantum violations. We prove that quantum theory only violates those NC inequalities whose exclusivity graphs contain, as induced subgraphs, odd cycles of length five or more, and/or their complements. In addition, we show that odd cycles are the exclusivity graphs of a well-known family of NC inequalities and that there is also a family of NC inequalities whose exclusivity graphs are the complements of odd cycles. We characterize the maximum noncontextual and quantum values of these inequalities, and provide evidence supporting the conjecture that the maximum quantum violation of these inequalities is exactly singled out by the exclusivity principle.

arXiv:1211.5825•Physical Review A•Sep 9, 2013•50 citations
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.
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)\mathrm{TH}({G}_{\text{CHSH}})TH(GCHSH​) is equal to the quantum set of the CHSH Bell inequality QCHSH{\mathcal{Q}}_{\text{CHSH}}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\mathcal{G}G and the NC CHSH inequality by a simple graph GGG, which is the shadow of the colored graph G\mathcal{G}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)\mathrm{TH}(G)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 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 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.
Bell nonlocality and quantum contextuality are two important resources which, however, behave very differently in many tasks where the quantum correlation has an edge over its classical counterpart. In this work, we directly compare these two behaviors, which via the Cabello-Severini-Winter graph-theoretical approach, can be associated with a same exclusivity graph. In particular, we consider the exclusivity graph that leads to I3322{I}_{3322}I3322​-type inequalities in the Bell and the contextual scenarios, respectively. We find that maximal violation of Bell inequality is around 6.251, and maximal violation of the noncontextuality inequality is around 6.588 for a five-dimensional system and 6.571 for a four-dimensional system, respectively. The results predict a gap of $\mathrm{\ensuremath{\Delta}}\ensuremath{\approx}0.32$ between quantum contextuality and Bell nonlocality. We then present an experimental observation of the gap by employing both the maximally entangled photon pairs from the spontaneous parametric down-conversion process and the single photons encoded into qudits from an intrinsic defect in gallium nitride. Our results will further deepen the understanding of different types of quantum correlations.
A fundamental problem is to understand why quantum theory only violates some noncontextuality (NC) inequalities and identify the physical principles that prevent higher-than-quantum violations. We prove that quantum theory only violates those NC inequalities whose exclusivity graphs contain, as induced subgraphs, odd cycles of length five or more, and/or their complements. In addition, we show that odd cycles are the exclusivity graphs of a well-known family of NC inequalities and that there is also a family of NC inequalities whose exclusivity graphs are the complements of odd cycles. We characterize the maximum noncontextual and quantum values of these inequalities, and provide evidence supporting the conjecture that the maximum quantum violation of these inequalities is exactly singled out by the exclusivity principle.