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:1912.11412 · Electronic Proceedings in Theoretical Computer Science

Contextuality and Expressivity of Non-locality

Sacha Huriot-Tattegrain, Mehdi Mhalla

Published Sep 6, 2021• 0 citations
arXivHTMLPDF

Abstract

Contextuality is often referred to as a generalization of non-locality. In this work, using the hypergraph approach for contextuality we show how to associate a contextual scenario to a general k-partite non local game, and consider the reverse direction: how and when is it possible to represent a general contextuality scenario as a non local game. Using the notion of conditional contextuality, we show that it is possible to embed any contextual scenario in a two players non local game. We also discuss different equivalences of contextuality scenarios and show that the construction used in the proof is not optimal by giving a simpler bipartite non local game when the contextual scenario is a graph instead of a general hypergraph.

DOI
10.4204/eptcs.340.8

Related papers

Revealing universal quantum contextuality through communication games

A. K. Pan

An ontological model of an operational theory is considered to be universally noncontextual if both preparation and measurement noncontextuality assumptions are satisfied in that model. In this report, we first generalize the logical proofs of quantum preparation and measurement contextuality for qubit system for any odd number of preparations and measurements. Based on the logical proof, we derive testable universally non-contextual inequalities violated by quantum theory. We then propose a class of two-party communication games and show that the average success probability of winning such games is solely linked to suitable Bell expression whose local bound is greater than universal non-contextual bound. Thus, for a given state, even if quantum theory does not exhibit non-locality, it may still reveal non-classicality by violating the universal non-contextual bound. Further, we consider a different communication game to demonstrate that for a given choices of observables in quantum theory, even if there is no logical proof of preparation and measurement contextuality exist, the universal quantum contextuality can be revealed through that communication game. Such a game thus test a weaker form of universal non-contextuality with minimal assumption.

arXiv:1912.10972•Scientific Reports•Nov 26, 2019•22 citations

Operator systems, contextuality and non-locality

M. Anoussis, Alexandros Chatzinikolaou, Ivan G. Todorov

We introduce an operator system, universal for the probabilistic models of a contextuality scenario, and identify its maximal C∗-cover via the right C∗-algebra of a canonical ternary ring of operators, arising from a hypergraph version of stochastic operator matrices. We study dilating contextuality scenarios, which have the property that each positive operator representation thereof admits a dilation to a projective representation on a larger Hilbert space, and characterise them via the equality of the aforementioned universal operator system and the operator system arising from the canonical generators of the respective hypergraph C∗-algebra. We characterise the no-signalling probabilistic models over a pair of contextuality scenarios of different types, which arise from either the positive operator representations or from the projective representations of these scenarios, in terms of states on operator system tensor products. Generalising the notion of a synchronous no-signalling correlation to the hypergraph framework, we define coherent probabilistic models associated with a given contextuality scenario and characterise various classes thereof via different types of traces of the hypergraph C∗-algebra, associated with the scenario. We establish several equivalent formulations of the Connes Embedding Problem in terms of no-signalling probabilistic models and hypergraph operator systems.

arXiv:2405.11152•Dissertationes Mathematicae•Oct 28, 2026•2 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

Probabilistic models on contextuality scenarios

Tobias Fritz, Anthony Leverrier, Ana Belén Sainz

We introduce a framework to describe probabilistic models in Bell experiments, and more generally in contextuality scenarios. Such a scenario is a hypergraph whose vertices represent elementary events and hyperedges correspond to measurements. A probabilistic model on such a scenario associates to each event a probability, in such a way that events in a given measurement have a total probability equal to one. We discuss the advantages of this framework, like the unification of the notions of contexuality and nonlocality, and give a short overview of results obtained elsewhere.

arXiv:1307.0145•Electronic Proceedings in Theoretical Computer Science•Dec 26, 2014•10 citations

Trade-off relations between Bell nonlocality and local Kochen–Specker contextuality in generalized Bell scenarios

Lucas Emanuel Antunes Porto, Gabriel Ruffolo, Rafael Rabelo +2 more

Abstract The relations between Bell nonlocality and Kochen–Specker contextuality have been subject of research from many different perspectives in the last decades. Recently, some interesting results on these relations have been explored in the so-called generalized Bell scenarios, that is, scenarios where Bell spatial separation (or agency independence) coexist with (at least one of the) parties’ ability to perform compatible measurements at each round of the experiment. When this party has an n-cycle compatiblity setup, it was first claimed that Bell nonlocality could not be concomitantly observed with contextuality at this party’s local experiment. However, by a more natural reading of the definition of locality, it turns out that both Bell nonlocality and local contextuality can, in fact, be jointly present. In spite of it, in this work we prove that in the simplest of those scenarios there cannot be arbitrary amounts of both of these two resources together. That is, in these cases we show that the violation of any Bell inequality limits the possible violations of any local noncontextuality inequality. We also explore this trade-off relation using quantifiers of nonlocality and contextuality, discussing how such a relation can be understood in terms of a ‘global’ notion of contextuality, and we study possible extensions of this result to other scenarios.

arXiv:2405.02964•New Journal of Physics•Aug 1, 2024•2 citations

A Computational Test of Contextuality and, Even Simpler Proofs of Quantumness

Atul Singh Arora, Kishor Bharti, Alexandru Cojocaru +1 more

Bell non-locality is a fundamental feature of quantum mechanics whereby measurements performed on “spatially separated” quantum systems can exhibit correlations that cannot be understood as revealing predetermined values. This is a special case of the more general phenomenon of “quantum contextuality”, which says that such correlations can occur even when the measurements are not necessarily on separate quantum systems, but are merely “compatible” (i.e. commuting). Crucially, while any non-local game yields an experiment that demonstrates quantum advantage by leveraging the “spatial separation” of two or more devices (and in fact several such demonstrations have been conducted successfully in recent years), the same is not true for quantum contextuality: finding the contextuality analogue of such an experiment is arguably one of the central open questions in the foundations of quantum mechanics. In this work, we show that an arbitrary contextuality game can be compiled into an “operational test of contextuality” involving a single quantum device, by only making the assumption that the device is computationally bounded. Our work is inspired by the recent work of Kalai et al. (STOC '23) that converts any non-local game into a classical test of quantum advantage with a single device. The central idea in their work is to use cryptography to enforce spatial separation within subsystems of a single quantum device. Our work can be seen as using cryptography to enforce “temporal separation”, i.e. to restrict communication between sequential measurements. Beyond contextuality, we employ our ideas to design a “proof of quantumness” that, to the best of our knowledge, is arguably even simpler than the ones proposed in the literature so far.

arXiv:2405.06787•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•9 citations
Contextuality is often referred to as a generalization of non-locality. In this work, using the hypergraph approach for contextuality we show how to associate a contextual scenario to a general k-partite non local game, and consider the reverse direction: how and when is it possible to represent a general contextuality scenario as a non local game. Using the notion of conditional contextuality, we show that it is possible to embed any contextual scenario in a two players non local game. We also discuss different equivalences of contextuality scenarios and show that the construction used in the proof is not optimal by giving a simpler bipartite non local game when the contextual scenario is a graph instead of a general hypergraph.
An ontological model of an operational theory is considered to be universally noncontextual if both preparation and measurement noncontextuality assumptions are satisfied in that model. In this report, we first generalize the logical proofs of quantum preparation and measurement contextuality for qubit system for any odd number of preparations and measurements. Based on the logical proof, we derive testable universally non-contextual inequalities violated by quantum theory. We then propose a class of two-party communication games and show that the average success probability of winning such games is solely linked to suitable Bell expression whose local bound is greater than universal non-contextual bound. Thus, for a given state, even if quantum theory does not exhibit non-locality, it may still reveal non-classicality by violating the universal non-contextual bound. Further, we consider a different communication game to demonstrate that for a given choices of observables in quantum theory, even if there is no logical proof of preparation and measurement contextuality exist, the universal quantum contextuality can be revealed through that communication game. Such a game thus test a weaker form of universal non-contextuality with minimal assumption.
We introduce an operator system, universal for the probabilistic models of a contextuality scenario, and identify its maximal C∗-cover via the right C∗-algebra of a canonical ternary ring of operators, arising from a hypergraph version of stochastic operator matrices. We study dilating contextuality scenarios, which have the property that each positive operator representation thereof admits a dilation to a projective representation on a larger Hilbert space, and characterise them via the equality of the aforementioned universal operator system and the operator system arising from the canonical generators of the respective hypergraph C∗-algebra. We characterise the no-signalling probabilistic models over a pair of contextuality scenarios of different types, which arise from either the positive operator representations or from the projective representations of these scenarios, in terms of states on operator system tensor products. Generalising the notion of a synchronous no-signalling correlation to the hypergraph framework, we define coherent probabilistic models associated with a given contextuality scenario and characterise various classes thereof via different types of traces of the hypergraph C∗-algebra, associated with the scenario. We establish several equivalent formulations of the Connes Embedding Problem in terms of no-signalling probabilistic models and hypergraph operator systems.
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.
We introduce a framework to describe probabilistic models in Bell experiments, and more generally in contextuality scenarios. Such a scenario is a hypergraph whose vertices represent elementary events and hyperedges correspond to measurements. A probabilistic model on such a scenario associates to each event a probability, in such a way that events in a given measurement have a total probability equal to one. We discuss the advantages of this framework, like the unification of the notions of contexuality and nonlocality, and give a short overview of results obtained elsewhere.
Abstract The relations between Bell nonlocality and Kochen–Specker contextuality have been subject of research from many different perspectives in the last decades. Recently, some interesting results on these relations have been explored in the so-called generalized Bell scenarios, that is, scenarios where Bell spatial separation (or agency independence) coexist with (at least one of the) parties’ ability to perform compatible measurements at each round of the experiment. When this party has an n-cycle compatiblity setup, it was first claimed that Bell nonlocality could not be concomitantly observed with contextuality at this party’s local experiment. However, by a more natural reading of the definition of locality, it turns out that both Bell nonlocality and local contextuality can, in fact, be jointly present. In spite of it, in this work we prove that in the simplest of those scenarios there cannot be arbitrary amounts of both of these two resources together. That is, in these cases we show that the violation of any Bell inequality limits the possible violations of any local noncontextuality inequality. We also explore this trade-off relation using quantifiers of nonlocality and contextuality, discussing how such a relation can be understood in terms of a ‘global’ notion of contextuality, and we study possible extensions of this result to other scenarios.
Bell non-locality is a fundamental feature of quantum mechanics whereby measurements performed on “spatially separated” quantum systems can exhibit correlations that cannot be understood as revealing predetermined values. This is a special case of the more general phenomenon of “quantum contextuality”, which says that such correlations can occur even when the measurements are not necessarily on separate quantum systems, but are merely “compatible” (i.e. commuting). Crucially, while any non-local game yields an experiment that demonstrates quantum advantage by leveraging the “spatial separation” of two or more devices (and in fact several such demonstrations have been conducted successfully in recent years), the same is not true for quantum contextuality: finding the contextuality analogue of such an experiment is arguably one of the central open questions in the foundations of quantum mechanics. In this work, we show that an arbitrary contextuality game can be compiled into an “operational test of contextuality” involving a single quantum device, by only making the assumption that the device is computationally bounded. Our work is inspired by the recent work of Kalai et al. (STOC '23) that converts any non-local game into a classical test of quantum advantage with a single device. The central idea in their work is to use cryptography to enforce spatial separation within subsystems of a single quantum device. Our work can be seen as using cryptography to enforce “temporal separation”, i.e. to restrict communication between sequential measurements. Beyond contextuality, we employ our ideas to design a “proof of quantumness” that, to the best of our knowledge, is arguably even simpler than the ones proposed in the literature so far.