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:1010.2163

(Non-)Contextuality of Physical Theories as an Axiom

Adán Cabello, Simone Severini B, Andreas Winter

Published Oct 11, 2010• 110 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1010.2163

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•336 citations

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•27 citations

Multigraph approach to quantum non-locality

Rafael Rabelo, Cristhiano Duarte, López Tarrida, Antonio José +2 more

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.

•Oct 8, 2014•19 citations

Uniqueness of all fundamental noncontextuality inequalities

Kishor Bharti, Atul Singh Arora, L. C. Kwek +1 more

Contextuality is one way of capturing the nonclassicality of quantum theory.The contextual nature of a theory is often witnessed via the violation of noncontextuality inequalities-certain linear inequalities involving probabilities of measurement events.Using the exclusivity graph approach (one of the two main graph theoretic approaches for studying contextuality), it was shown [Cabello et al.Phys. Rev. A 88, 032104 (2013); Chudnovsky et al.Ann. Math. 164, 51 (2006)] that a necessary and sufficient condition for witnessing contextuality is the presence of an odd number of events (greater than three) which are either cyclically or anticyclically exclusive.Thus, the noncontextuality inequalities the underlying exclusivity structure of which is as stated, either cyclic or anticyclic, are fundamental to quantum theory.We show that there is a unique noncontextuality inequality for each nontrivial cycle and anticycle.In addition to the foundational interest, we expect this to aid the understanding of contextuality as a resource to quantum computing and its applications to local self-testing.

arXiv:1811.05294•Physical Review Research•Jul 2, 2020•0 citations

On the applicability of Kolmogorov's theory of probability to the description of quantum phenomena. Part II: Bell inequalities

Maik Reddiger

Among the various "no-go theorems" in the foundations of quantum mechanics, Bell inequalities are among the few, which do not implicitly rely on the mathematical structure of quantum mechanics. Instead, Bell inequalities are commonly understood to rest on Kolmogorov's theory of probability and a "locality" assumption. Physical evidence supporting their violation is hence taken as evidence against at least one of these two assumptions. This work provides a comprehensive analysis of the physical debate on Bell inequalities from the point of view of Kolmogorov's theory of probability, focusing on the Bell-Clauser-Horn-Shimony-Holt inequality (BCHSH inequality). The central contribution is the motivation and mathematical study of the notion of contextuality in Bell experiments: in so-called contextual Bell models the detectors themselves behave randomly and the distribution of the random detector parameters depends on the chosen detector settings. It is shown how even "classical" Bell experiments motivate such a description. The need to account for contextuality was pointed out before by de la Peña, Cetto, Brody, Lochak, Bohm, Hiley and others. A broad class of contextual models is proven to satisfy the BCHSH inequality, thereby generalizing a previous result by Gill and Lambare. Nonetheless, even under strong locality requirements, contextual Bell models may violate the BCHSH inequality: based on work by Popescu and Rohrlich, we consider a "proof of concept" example exhibiting the maximum possible violation. Contrary to the much debated "loopholes" in empirical tests of Bell inequalities, contextuality thus reveals a conceptual misunderstanding in the physical conclusions commonly drawn from Bell inequality violations.

quant-pharXiv:2609.31075•Sep 28, 2026•0 citations

Conditions for logical contextuality and nonlocality

Leonardo Santos, Bárbara Amaral

Contextuality and nonlocality are nonclassical properties exhibited by quantum statistics whose implications profoundly impact both the foundations and applications of quantum theory. In this paper we provide some insights into logical contextuality and inequality-free proofs. The former can be understood as the possibility version of contextuality, while the latter refers to proofs of quantum contextuality and nonlocality that are not based on violations of some noncontextuality (or Bell) inequality. By ``possibilistic'' we mean a description in terms of possibilities for the outcomes, which are Boolean variables assuming value one when the corresponding probability is strictly larger than zero and zero otherwise. The present work aims to build a bridge between these two concepts from what we call possibilistic paradoxes, which are sets of possibilistic conditions whose occurrence implies contextuality and nonlocality. As the main result, we demonstrate the existence of possibilistic paradoxes whose occurrence is a necessary and sufficient condition for logical contextuality in a very important class of scenarios. Finally, we discuss some interesting consequences arising from the completeness of these possibilistic paradoxes.

arXiv:2011.04111•Physical Review A•Aug 4, 2021•7 citations
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.
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.
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.
Contextuality is one way of capturing the nonclassicality of quantum theory.The contextual nature of a theory is often witnessed via the violation of noncontextuality inequalities-certain linear inequalities involving probabilities of measurement events.Using the exclusivity graph approach (one of the two main graph theoretic approaches for studying contextuality), it was shown [Cabello et al.Phys. Rev. A 88, 032104 (2013); Chudnovsky et al.Ann. Math. 164, 51 (2006)] that a necessary and sufficient condition for witnessing contextuality is the presence of an odd number of events (greater than three) which are either cyclically or anticyclically exclusive.Thus, the noncontextuality inequalities the underlying exclusivity structure of which is as stated, either cyclic or anticyclic, are fundamental to quantum theory.We show that there is a unique noncontextuality inequality for each nontrivial cycle and anticycle.In addition to the foundational interest, we expect this to aid the understanding of contextuality as a resource to quantum computing and its applications to local self-testing.
Among the various "no-go theorems" in the foundations of quantum mechanics, Bell inequalities are among the few, which do not implicitly rely on the mathematical structure of quantum mechanics. Instead, Bell inequalities are commonly understood to rest on Kolmogorov's theory of probability and a "locality" assumption. Physical evidence supporting their violation is hence taken as evidence against at least one of these two assumptions. This work provides a comprehensive analysis of the physical debate on Bell inequalities from the point of view of Kolmogorov's theory of probability, focusing on the Bell-Clauser-Horn-Shimony-Holt inequality (BCHSH inequality). The central contribution is the motivation and mathematical study of the notion of contextuality in Bell experiments: in so-called contextual Bell models the detectors themselves behave randomly and the distribution of the random detector parameters depends on the chosen detector settings. It is shown how even "classical" Bell experiments motivate such a description. The need to account for contextuality was pointed out before by de la Peña, Cetto, Brody, Lochak, Bohm, Hiley and others. A broad class of contextual models is proven to satisfy the BCHSH inequality, thereby generalizing a previous result by Gill and Lambare. Nonetheless, even under strong locality requirements, contextual Bell models may violate the BCHSH inequality: based on work by Popescu and Rohrlich, we consider a "proof of concept" example exhibiting the maximum possible violation. Contrary to the much debated "loopholes" in empirical tests of Bell inequalities, contextuality thus reveals a conceptual misunderstanding in the physical conclusions commonly drawn from Bell inequality violations.
Contextuality and nonlocality are nonclassical properties exhibited by quantum statistics whose implications profoundly impact both the foundations and applications of quantum theory. In this paper we provide some insights into logical contextuality and inequality-free proofs. The former can be understood as the possibility version of contextuality, while the latter refers to proofs of quantum contextuality and nonlocality that are not based on violations of some noncontextuality (or Bell) inequality. By ``possibilistic'' we mean a description in terms of possibilities for the outcomes, which are Boolean variables assuming value one when the corresponding probability is strictly larger than zero and zero otherwise. The present work aims to build a bridge between these two concepts from what we call possibilistic paradoxes, which are sets of possibilistic conditions whose occurrence implies contextuality and nonlocality. As the main result, we demonstrate the existence of possibilistic paradoxes whose occurrence is a necessary and sufficient condition for logical contextuality in a very important class of scenarios. Finally, we discuss some interesting consequences arising from the completeness of these possibilistic paradoxes.