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:1512.05048 · Physical Review A

Graph-theoretic strengths of contextuality

Nadish de Silva

Published Mar 9, 2017• 18 citations
arXivHTMLPDF

Abstract

Cabello-Severini-Winter and Abramsky-Hardy (building on the framework of Abramsky-Brandenburger) both provide classes of Bell and contextuality inequalities for very general experimental scenarios using vastly different mathematical techniques. We review both approaches, carefully detail the links between them, and give simple, graph-theoretic methods for finding inequality-free proofs of nonlocality and contextuality and for finding states exhibiting strong nonlocality and/or contextuality. Finally, we apply these methods to concrete examples in stabilizer quantum mechanics relevant to understanding contextuality as a resource in quantum computation.

DOI
10.1103/physreva.95.032108

Related papers

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•5 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

4 A Combinatorial Approach to Nonlocality and Contextuality

T. A. Fritz, Anthony Leverrier, Ana Belén Sainz

So far, most of the literature on (quantum) contextuality and the Kochen–\nSpecker theorem seems either to concern particular examples of contextuality, or be\nconsidered as quantum logic. Here, we develop a general formalism for contextuality\nscenarios based on the combinatorics of hypergraphs, which significantly refines a similar\nrecent approach by Cabello, Severini and Winter (CSW). In contrast to CSW, we\nexplicitly include the normalization of probabilities, which gives us a much finer control\nover the various sets of probabilistic models like classical, quantum and generalized\nprobabilistic. In particular, our framework specializes to (quantum) nonlocality in the\ncase of Bell scenarios, which arise very naturally from a certain product of contextuality\nscenarios due to Foulis and Randall. In the spirit of CSW, we find close relationships to\nseveral graph invariants. The recently proposed Local Orthogonality principle turns out\nto be a special case of a general principle for contextuality scenarios related to the Shannon\ncapacity of graphs. Our results imply that it is strictly dominated by a low level of\nthe Navascués–Pironio–Acín hierarchy of semidefinite programs, which we also apply\nto contextuality scenarios.\nWe derive a wealth of results in our framework, many of these relating to quantum\nand supraquantum contextuality and nonlocality, and state numerous open problems.\nFor example, we show that the set of quantum models on a con

•Jan 1, 2015•140 citations

Possibilistic (and other) notions of contextuality

Andrew W. Simmons

Since Bell, Kochen and Specker formulated the first notions of contextuality, a number of frameworks have been created to help make philosophical and mathematical sense of the concept. Two of the most common are the Equivalence-based approach due to Spekkens, and the Sheaf-theoretic framework of Abramsky and Brandenburger. Each of these can support a hierarchy of strengths of contextuality, which can include possibilistic concepts. This thesis will explore the differences between the two approaches, and explore what can be demonstrated by using weaker notions of noncontextuality. Notions of noncontextuality are important for proving no-go theorems which highlight that many properties that are true of classical mechanics fail to be compatible with quantum predictions. Often, the notions of noncontextuality used are very strong assumptions, and even weaker flavours of noncontextuality can be used to draw the same, or similar conclusions. An important class of such notions are, possibilistic assumptions that only care about whether or not events are possible or impossible, rather than the exact Born rule probabilities that are applied to events. Even these weaker notions are often impossible to resolve with the logical structure and predictions of quantum theory. Contextuality has been demonstrated to be a resource for many quantum computational operations, and the contextual fraction has been shown to be an important resource. We introduce a metric that can differentiate between different quantum mechanical scenarios with contextual fraction 1, and demonstrate analogues of CHSH and Tsirelson bounds for this quantity. We also investigate the computational complexity of calculating the values of some metrics for nonlocality and contextuality, completing the classification of possibilistic nonlocality scenarios, as well as other metrics of nonlocality analogous to our metric of maximal contextuality.

•Sep 1, 2018•2 citations

Connecting Quantum Contextuality and Nonlocality

Jianqi Sheng, Dongkai Zhang, Lixiang Chen

Quantum theory departs from classical physics in its treatment of correlations, most prominently through the phenomena of contextuality and nonlocality. Once regarded primarily as foundational curiosities, these effects are now understood as key operational resources for quantum computation, communication, and simulation. Although traditionally investigated in distinct settings, recent theoretical and experimental advances have revealed deep conceptual, mathematical, and operational connections between them. This review presents a unified perspective on these developments based on sheaf-theoretic and graph-theoretic frameworks, which provide theory-independent characterizations of statistical correlations. These approaches clarify the structural relationship between contextuality and nonlocality, facilitate the formulation of experimentally testable inequalities, and guide implementations in realistic physical platforms, with particular emphasis on photonic systems. By bridging abstract theoretical structures and concrete experimental realizations, this review sheds light on the nonclassical foundations of quantum correlations and their emerging role in quantum technologies.

quant-pharXiv:2602.23221•Feb 27, 2026•0 citations

Contextuality, Locality, and the Interpretation of Bell Violations

Partha Ghose

The ontological significance of violations of Bell inequalities is reexamined. Bell's theorem admits several mathematically equivalent formulations that support different interpretive perspectives. The present paper develops one such perspective using contextuality, the sheaf-theoretic framework of Abramsky and Brandenburger, and Nelson's stochastic mechanics.

quant-pharXiv:2604.26916•Journal of Theoretical Experimental and Applied Physics•Apr 30, 2026•0 citations
Cabello-Severini-Winter and Abramsky-Hardy (building on the framework of Abramsky-Brandenburger) both provide classes of Bell and contextuality inequalities for very general experimental scenarios using vastly different mathematical techniques. We review both approaches, carefully detail the links between them, and give simple, graph-theoretic methods for finding inequality-free proofs of nonlocality and contextuality and for finding states exhibiting strong nonlocality and/or contextuality. Finally, we apply these methods to concrete examples in stabilizer quantum mechanics relevant to understanding contextuality as a resource in quantum computation.
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.
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.
So far, most of the literature on (quantum) contextuality and the Kochen–\nSpecker theorem seems either to concern particular examples of contextuality, or be\nconsidered as quantum logic. Here, we develop a general formalism for contextuality\nscenarios based on the combinatorics of hypergraphs, which significantly refines a similar\nrecent approach by Cabello, Severini and Winter (CSW). In contrast to CSW, we\nexplicitly include the normalization of probabilities, which gives us a much finer control\nover the various sets of probabilistic models like classical, quantum and generalized\nprobabilistic. In particular, our framework specializes to (quantum) nonlocality in the\ncase of Bell scenarios, which arise very naturally from a certain product of contextuality\nscenarios due to Foulis and Randall. In the spirit of CSW, we find close relationships to\nseveral graph invariants. The recently proposed Local Orthogonality principle turns out\nto be a special case of a general principle for contextuality scenarios related to the Shannon\ncapacity of graphs. Our results imply that it is strictly dominated by a low level of\nthe Navascués–Pironio–Acín hierarchy of semidefinite programs, which we also apply\nto contextuality scenarios.\nWe derive a wealth of results in our framework, many of these relating to quantum\nand supraquantum contextuality and nonlocality, and state numerous open problems.\nFor example, we show that the set of quantum models on a con
Since Bell, Kochen and Specker formulated the first notions of contextuality, a number of frameworks have been created to help make philosophical and mathematical sense of the concept. Two of the most common are the Equivalence-based approach due to Spekkens, and the Sheaf-theoretic framework of Abramsky and Brandenburger. Each of these can support a hierarchy of strengths of contextuality, which can include possibilistic concepts. This thesis will explore the differences between the two approaches, and explore what can be demonstrated by using weaker notions of noncontextuality. Notions of noncontextuality are important for proving no-go theorems which highlight that many properties that are true of classical mechanics fail to be compatible with quantum predictions. Often, the notions of noncontextuality used are very strong assumptions, and even weaker flavours of noncontextuality can be used to draw the same, or similar conclusions. An important class of such notions are, possibilistic assumptions that only care about whether or not events are possible or impossible, rather than the exact Born rule probabilities that are applied to events. Even these weaker notions are often impossible to resolve with the logical structure and predictions of quantum theory. Contextuality has been demonstrated to be a resource for many quantum computational operations, and the contextual fraction has been shown to be an important resource. We introduce a metric that can differentiate between different quantum mechanical scenarios with contextual fraction 1, and demonstrate analogues of CHSH and Tsirelson bounds for this quantity. We also investigate the computational complexity of calculating the values of some metrics for nonlocality and contextuality, completing the classification of possibilistic nonlocality scenarios, as well as other metrics of nonlocality analogous to our metric of maximal contextuality.
Quantum theory departs from classical physics in its treatment of correlations, most prominently through the phenomena of contextuality and nonlocality. Once regarded primarily as foundational curiosities, these effects are now understood as key operational resources for quantum computation, communication, and simulation. Although traditionally investigated in distinct settings, recent theoretical and experimental advances have revealed deep conceptual, mathematical, and operational connections between them. This review presents a unified perspective on these developments based on sheaf-theoretic and graph-theoretic frameworks, which provide theory-independent characterizations of statistical correlations. These approaches clarify the structural relationship between contextuality and nonlocality, facilitate the formulation of experimentally testable inequalities, and guide implementations in realistic physical platforms, with particular emphasis on photonic systems. By bridging abstract theoretical structures and concrete experimental realizations, this review sheds light on the nonclassical foundations of quantum correlations and their emerging role in quantum technologies.