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

Polyteam logics for quantum contextuality

Loan Le Maguet

math.LOquant-phSubmitted Oct 31, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

Abstract

We introduce logics of dependence and independence over polyteams (that is, databases with multiple relation schemes), in a similar way as in arXiv:1704.02158v3 [cs.LO]. On this basis, we develop a logical framework in which we can express (in formulas) relevant properties about the statistics of a repeated quantum experiment. In this framework, we formalize Bell's theorem, and the Kochen-Specker theorem as failure of logical entailments, as it was suggested in arXiv:2107.10817v3 [math.LO]. The key feature of polyteam logics in action here is their power to express both local and global properties, with respect to the set of possible measurements. The point of this is at least twofold. Firstly, as in arXiv:1102.0264v7 [quant-ph], it gives a high-level (information-theoretic) understanding of these physical phenomena, that is not intrinsic to the physical objects involved. Secondly, since logical entailment is often (partially) axiomatizable, this framework incites us to tackle the question of contextuality computationally. We also define semiring-weighted polyteams along with logics on them, and use them to recover the probabilistic versions of the contextuality theorems mentioned above.

AI Summary

The paper asks how quantum contextuality can be expressed in dependence and independence logics whose semantics describe several measurement contexts simultaneously. It represents an experiment as a *polyteam*: one table of possible outcomes per maximal compatible measurement context, with separate variables for overlapping measurements. This accommodates contexts of different sizes. It gives formulas for no-signalling, determinism, parameter independence, outcome independence, and context-independent hidden-variable values. It establishes that admitting a global outcome table is equivalent to admitting a deterministic hidden-variable realization, and to admitting a locally realistic realization. Bell and Kochen–Specker contextuality are then formulated as failures of logical entailment, $QM\not\models GS$ and $QM\not\models NSC$. The constructions use Hardy’s model and an 18-measurement, nine-context Kochen–Specker configuration; the latter’s contextuality follows from a parity argument. Quantum realizability is supplied through Hilbert-space constructions and encoded by a dedicated atom $QM$, rather than derived within the dependence logic. The framework is extended to semiring-weighted polyteams, including probabilistic models, with results connecting weighted formulas to their possibilistic supports. Deterministic and locally realistic realizations are shown equivalent for rational probabilities; extending this proof to real probabilities is left open. The formula for absence of strong contextuality uses a temporary restriction excluding empty component teams. Computational contextuality tests, partial axiomatizations, expressive-power comparisons, and extensions beyond positive semirings are deferred to future work.

No sign of AI-generated textIncrementalPossible errorUnclear writing

Central claim may not hold: The formula claimed to characterize absence of strong contextuality is universally true under the paper's original semantics, and its characterization requires a later change to the permitted splits. The Kochen–Specker section's claim that ONE(M_KS) ∧ NS entails quantum realizability has an incorrect density-matrix proof and a displayed witness whose three pairwise-compatible measurements require impossible pairwise perfect anticorrelations. The written definition underlying QM omits positivity, within-context commutativity, and state-vector normalization conditions needed to justify its probability calculations. The rational determinization construction incorrectly uses a gcd of probability denominators to obtain integer partition sizes, although an lcm fixes that step.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
Article produced from the Master thesis of the author

Related papers

The Logic of Contextuality

Samson Abramsky, Rui Soares Barbosa

Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.

arXiv:2011.03064•Leibniz international proceedings in informatics•Nov 5, 2020•22 citations

Contextuality under weak assumptions

Andrew W. Simmons, Joel J. Wallman, Hakop Pashayan +2 more

The presence of contextuality in quantum theory was first highlighted by Bell, Kochen and Specker, who discovered that for quantum systems of three or more dimensions, measurements could not be viewed as deterministically revealing pre-existing properties of the system. More precisely, no model can assign deterministic outcomes to the projectors of a quantum measurement in a way that depends only on the projector and not the context (the full set of projectors) in which it appeared, despite the fact that the Born rule probabilities associated with projectors are independent of the context. A more general, operational definition of contextuality introduced by Spekkens, which we will term 'probabilistic contextuality', drops the assumption of determinism and allows for operations other than measurements to be considered contextual. Even two-dimensional quantum mechanics can be shown to be contextual under this generalised notion. Probabilistic noncontextuality represents the postulate that elements of an operational theory that cannot be distinguished from each other based on the statistics of arbitrarily many repeated experiments (they give rise to the same operational probabilities) are ontologically identical. In this paper, we introduce a framework that enables us to distinguish between different noncontextuality assumptions in terms of the relationships between the ontological representations of objects in the theory given a certain relation between their operational representations. This framework can be used to motivate and define a 'possibilistic' analogue, encapsulating the idea that elements of an operational theory that cannot be unambiguously distinguished operationally can also not be unambiguously distinguished ontologically. We then prove that possibilistic noncontextuality is equivalent to an alternative notion of noncontextuality proposed by Hardy. Finally, we demonstrate that these weaker noncontextuality assumptions are sufficient to prove alternative versions of known 'no-go' theorems that constrain ψ -epistemic models for quantum mechanics.

arXiv:1610.06897•New Journal of Physics•Feb 9, 2017•10 citations

Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem

Victoria J Wright, Ravi Kunjwal

The Kochen–Specker (KS) theorem reveals the nonclassicality of single quantum systems. In contrast, Bell's theorem and entanglement concern the nonclassicality of composite quantum systems. Accordingly, unlike incompatibility, entanglement and Bell non-locality are not necessary to demonstrate KS-contextuality. However, here we find that for multiqubit systems, entanglement and non-locality are both essential to proofs of the Kochen–Specker theorem. Firstly, we show that unentangled measurements (a strict superset of local measurements) can never yield a logical (state-independent) proof of the KS theorem for multiqubit systems. In particular, unentangled but nonlocal measurements—whose eigenstates exhibit ''nonlocality without entanglement"—are insufficient for such proofs. This also implies that proving Gleason's theorem on a multiqubit system necessarily requires entangled projections, as shown by Wallach [Contemp Math, 305: 291-298 (2002)]. Secondly, we show that a multiqubit state admits a statistical (state-dependent) proof of the KS theorem if and only if it can violate a Bell inequality with projective measurements. We also establish the relationship between entanglement and the theorems of Kochen–Specker and Gleason more generally in multiqudit systems by constructing new examples of KS sets. Finally, we discuss how our results shed new light on the role of multiqubit contextuality as a resource within the paradigm of quantum computation with state injection.

arXiv:2109.13594•Quantum•Jan 19, 2023•13 citations

An algebraic characterisation of Kochen-Specker contextuality

Markus Frembs

Contextuality is a key distinguishing feature between classical and quantum physics. It expresses a fundamental obstruction to describing quantum theory using classical concepts. In turn, understood as a resource for quantum computation, it is expected to hold the key to quantum advantage. Yet, despite its long recognised importance in quantum foundations and, more recently, in quantum computation, the structural essence of contextuality has remained somewhat elusive - different frameworks address different aspects of the phenomenon, yet their precise relationship often remains unclear. This issue already looms large at the level of the Bell-Kochen-Specker theorem: while traditional proofs proceed by showing the nonexistence of valuations, the notion of state-independent contextuality in the marginal approach allows to prove contextuality from seemingly weaker assumptions. In the light of this, and at the absence of a unified mathematical framework for Kochen-Specker contextuality, the original algebraic approach has been widely abandoned, in favour of the study of contextual correlations. Here, we reinstate the algebraic perspective on contextuality. Concretely, by building on the novel concept of context connections, we reformulate the algebraic relations between observables originally postulated by Kochen and Specker, and we explicitly demonstrate their consistency with the notion of state-independent contextuality. In the present paper, we focus on the new conceptual ideas and discuss them in the concrete setting of spin-1 observables, specifically those in the example of [S. Yu and C.H. Oh, Phys. Rev. Lett., 108, 030402 (2012)]; in a companion paper, we generalise these ideas, obtain a complete characterisation of Kochen-Specker contextuality and provide a detailed comparison with the related notions of contextuality in the marginal and graph-theoretic approach.

arXiv:2408.16764•Aug 29, 2024•5 citations

Contextuality beyond the Kochen-Specker theorem

Ravi Kunjwal

When it isn't possible to tell two distinct experimental procedures apart purely from their input/output statistics, then it seems a plausible hypothesis that the two procedures must be physically identical. We call such a hypothesis "noncontextuality", an instance of Leibniz's principle of the identity of indiscernibles. Read in the contrapositive, this hypothesis entails that any physical distinctions between two experimental procedures must necessarily lead to a difference in their operational statistics. The results I present in this thesis concern the failure of this hypothesis -- a failure dubbed "contextuality" -- when one tries to embed an operational theory (such as quantum theory) in the ontological models framework. The Kochen-Specker theorem demonstrates the failure of noncontextuality for deterministic ontological models of quantum theory, i.e., those ontological models where the ontic/physical state of the system fixes the outcome of any projective measurement on the system in a deterministic manner. This thesis goes beyond the Kochen-Specker (KS) theorem by asking what operational facts must be verified in experiments to conclude that Nature does not admit noncontextual ontological models, not even indeterministic ones. This leads to noncontextuality inequalities that are robust to noise in the preparations and measurements. In the particular case of quantum theory, these inequalities are meaningful even when unsharp measurements (or POVMs) are allowed, a feature not shared by the traditional approach to KS-noncontextuality where unsharp measurements are excluded by fiat: allowing them renders even trivial POVMs (proportional to identity) maximally KS-contextual. The sense in which trivial POVMs are indeed "trivial" (or "noncontextual") is clear in our approach: they are simply too noisy to lead to violation of our noncontextuality inequalities.

arXiv:1612.07250•Dec 21, 2016•33 citations

Quantumness via Discrete Structures

Ravi Kunjwal

Quantum theory departs from classical probabilistic theories in foundational ways. These departures--termed quantumness here--power quantum information and computation. This thesis charts the role of discrete structures in assessing quantumness, synthesizing elements of my postdoctoral research through this lens. After an introduction to the necessary background concepts, I present my work under three broad categories. First, I present work on contextuality that extensively relies on (undirected) graphs and hypergraphs as the discrete structures of interest; more specifically, it relies on invariants associated with them. This work includes Kochen-Specker (KS) contextuality and its operationalization to generalized contextuality, expressed via (hyper)graph-theoretic frameworks. I also present work on KS-contextuality in multiqubit systems and an application of generalized contextuality to a one-shot communication task, both of which rely on hypergraphs. Second, I present work on causality, where the discrete structures of interest are directed graphs. This includes work on indefinite causal order, specifically its connections to the gap between local operations and classical communication (LOCC) and separable operations (SEP), and a device-independent notion of nonclassicality--termed antinomicity--that generalizes Bell nonlocality without global causal assumptions. Finally, I present work on the incompatibility of quantum measurements, its connection to Bell nonlocality, and its role in discriminating between quantum and almost quantum correlations in the single-system setting. The discrete structures of interest here are hypergraphs that model joint measurability relations between quantum measurements. I conclude with a summary and an overview of work that is not covered in this thesis.

quant-pharXiv:2512.10063•Dec 12, 2025•0 citations
We introduce logics of dependence and independence over polyteams (that is, databases with multiple relation schemes), in a similar way as in arXiv:1704.02158v3 [cs.LO]. On this basis, we develop a logical framework in which we can express (in formulas) relevant properties about the statistics of a repeated quantum experiment. In this framework, we formalize Bell's theorem, and the Kochen-Specker theorem as failure of logical entailments, as it was suggested in arXiv:2107.10817v3 [math.LO]. The key feature of polyteam logics in action here is their power to express both local and global properties, with respect to the set of possible measurements. The point of this is at least twofold. Firstly, as in arXiv:1102.0264v7 [quant-ph], it gives a high-level (information-theoretic) understanding of these physical phenomena, that is not intrinsic to the physical objects involved. Secondly, since logical entailment is often (partially) axiomatizable, this framework incites us to tackle the question of contextuality computationally. We also define semiring-weighted polyteams along with logics on them, and use them to recover the probabilistic versions of the contextuality theorems mentioned above.
The paper asks how quantum contextuality can be expressed in dependence and independence logics whose semantics describe several measurement contexts simultaneously. It represents an experiment as a polyteam: one table of possible outcomes per maximal compatible measurement context, with separate variables for overlapping measurements. This accommodates contexts of different sizes.
It gives formulas for no-signalling, determinism, parameter independence, outcome independence, and context-independent hidden-variable values. It establishes that admitting a global outcome table is equivalent to admitting a deterministic hidden-variable realization, and to admitting a locally realistic realization. Bell and Kochen–Specker contextuality are then formulated as failures of logical entailment, QM⊭GSQM\not\models GSQM⊨GS and QM⊭NSCQM\not\models NSCQM⊨NSC. The constructions use Hardy’s model and an 18-measurement, nine-context Kochen–Specker configuration; the latter’s contextuality follows from a parity argument. Quantum realizability is supplied through Hilbert-space constructions and encoded by a dedicated atom QMQMQM, rather than derived within the dependence logic.
The framework is extended to semiring-weighted polyteams, including probabilistic models, with results connecting weighted formulas to their possibilistic supports. Deterministic and locally realistic realizations are shown equivalent for rational probabilities; extending this proof to real probabilities is left open. The formula for absence of strong contextuality uses a temporary restriction excluding empty component teams. Computational contextuality tests, partial axiomatizations, expressive-power comparisons, and extensions beyond positive semirings are deferred to future work.
Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.
The presence of contextuality in quantum theory was first highlighted by Bell, Kochen and Specker, who discovered that for quantum systems of three or more dimensions, measurements could not be viewed as deterministically revealing pre-existing properties of the system. More precisely, no model can assign deterministic outcomes to the projectors of a quantum measurement in a way that depends only on the projector and not the context (the full set of projectors) in which it appeared, despite the fact that the Born rule probabilities associated with projectors are independent of the context. A more general, operational definition of contextuality introduced by Spekkens, which we will term 'probabilistic contextuality', drops the assumption of determinism and allows for operations other than measurements to be considered contextual. Even two-dimensional quantum mechanics can be shown to be contextual under this generalised notion. Probabilistic noncontextuality represents the postulate that elements of an operational theory that cannot be distinguished from each other based on the statistics of arbitrarily many repeated experiments (they give rise to the same operational probabilities) are ontologically identical. In this paper, we introduce a framework that enables us to distinguish between different noncontextuality assumptions in terms of the relationships between the ontological representations of objects in the theory given a certain relation between their operational representations. This framework can be used to motivate and define a 'possibilistic' analogue, encapsulating the idea that elements of an operational theory that cannot be unambiguously distinguished operationally can also not be unambiguously distinguished ontologically. We then prove that possibilistic noncontextuality is equivalent to an alternative notion of noncontextuality proposed by Hardy. Finally, we demonstrate that these weaker noncontextuality assumptions are sufficient to prove alternative versions of known 'no-go' theorems that constrain ψ -epistemic models for quantum mechanics.
The Kochen–Specker (KS) theorem reveals the nonclassicality of single quantum systems. In contrast, Bell's theorem and entanglement concern the nonclassicality of composite quantum systems. Accordingly, unlike incompatibility, entanglement and Bell non-locality are not necessary to demonstrate KS-contextuality. However, here we find that for multiqubit systems, entanglement and non-locality are both essential to proofs of the Kochen–Specker theorem. Firstly, we show that unentangled measurements (a strict superset of local measurements) can never yield a logical (state-independent) proof of the KS theorem for multiqubit systems. In particular, unentangled but nonlocal measurements—whose eigenstates exhibit ''nonlocality without entanglement"—are insufficient for such proofs. This also implies that proving Gleason's theorem on a multiqubit system necessarily requires entangled projections, as shown by Wallach [Contemp Math, 305: 291-298 (2002)]. Secondly, we show that a multiqubit state admits a statistical (state-dependent) proof of the KS theorem if and only if it can violate a Bell inequality with projective measurements. We also establish the relationship between entanglement and the theorems of Kochen–Specker and Gleason more generally in multiqudit systems by constructing new examples of KS sets. Finally, we discuss how our results shed new light on the role of multiqubit contextuality as a resource within the paradigm of quantum computation with state injection.
Contextuality is a key distinguishing feature between classical and quantum physics. It expresses a fundamental obstruction to describing quantum theory using classical concepts. In turn, understood as a resource for quantum computation, it is expected to hold the key to quantum advantage. Yet, despite its long recognised importance in quantum foundations and, more recently, in quantum computation, the structural essence of contextuality has remained somewhat elusive - different frameworks address different aspects of the phenomenon, yet their precise relationship often remains unclear. This issue already looms large at the level of the Bell-Kochen-Specker theorem: while traditional proofs proceed by showing the nonexistence of valuations, the notion of state-independent contextuality in the marginal approach allows to prove contextuality from seemingly weaker assumptions. In the light of this, and at the absence of a unified mathematical framework for Kochen-Specker contextuality, the original algebraic approach has been widely abandoned, in favour of the study of contextual correlations. Here, we reinstate the algebraic perspective on contextuality. Concretely, by building on the novel concept of context connections, we reformulate the algebraic relations between observables originally postulated by Kochen and Specker, and we explicitly demonstrate their consistency with the notion of state-independent contextuality. In the present paper, we focus on the new conceptual ideas and discuss them in the concrete setting of spin-1 observables, specifically those in the example of [S. Yu and C.H. Oh, Phys. Rev. Lett., 108, 030402 (2012)]; in a companion paper, we generalise these ideas, obtain a complete characterisation of Kochen-Specker contextuality and provide a detailed comparison with the related notions of contextuality in the marginal and graph-theoretic approach.
When it isn't possible to tell two distinct experimental procedures apart purely from their input/output statistics, then it seems a plausible hypothesis that the two procedures must be physically identical. We call such a hypothesis "noncontextuality", an instance of Leibniz's principle of the identity of indiscernibles. Read in the contrapositive, this hypothesis entails that any physical distinctions between two experimental procedures must necessarily lead to a difference in their operational statistics. The results I present in this thesis concern the failure of this hypothesis -- a failure dubbed "contextuality" -- when one tries to embed an operational theory (such as quantum theory) in the ontological models framework. The Kochen-Specker theorem demonstrates the failure of noncontextuality for deterministic ontological models of quantum theory, i.e., those ontological models where the ontic/physical state of the system fixes the outcome of any projective measurement on the system in a deterministic manner. This thesis goes beyond the Kochen-Specker (KS) theorem by asking what operational facts must be verified in experiments to conclude that Nature does not admit noncontextual ontological models, not even indeterministic ones. This leads to noncontextuality inequalities that are robust to noise in the preparations and measurements. In the particular case of quantum theory, these inequalities are meaningful even when unsharp measurements (or POVMs) are allowed, a feature not shared by the traditional approach to KS-noncontextuality where unsharp measurements are excluded by fiat: allowing them renders even trivial POVMs (proportional to identity) maximally KS-contextual. The sense in which trivial POVMs are indeed "trivial" (or "noncontextual") is clear in our approach: they are simply too noisy to lead to violation of our noncontextuality inequalities.
Quantum theory departs from classical probabilistic theories in foundational ways. These departures--termed quantumness here--power quantum information and computation. This thesis charts the role of discrete structures in assessing quantumness, synthesizing elements of my postdoctoral research through this lens. After an introduction to the necessary background concepts, I present my work under three broad categories. First, I present work on contextuality that extensively relies on (undirected) graphs and hypergraphs as the discrete structures of interest; more specifically, it relies on invariants associated with them. This work includes Kochen-Specker (KS) contextuality and its operationalization to generalized contextuality, expressed via (hyper)graph-theoretic frameworks. I also present work on KS-contextuality in multiqubit systems and an application of generalized contextuality to a one-shot communication task, both of which rely on hypergraphs. Second, I present work on causality, where the discrete structures of interest are directed graphs. This includes work on indefinite causal order, specifically its connections to the gap between local operations and classical communication (LOCC) and separable operations (SEP), and a device-independent notion of nonclassicality--termed antinomicity--that generalizes Bell nonlocality without global causal assumptions. Finally, I present work on the incompatibility of quantum measurements, its connection to Bell nonlocality, and its role in discriminating between quantum and almost quantum correlations in the single-system setting. The discrete structures of interest here are hypergraphs that model joint measurability relations between quantum measurements. I conclude with a summary and an overview of work that is not covered in this thesis.