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

Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption

Stefan Trandafir, Adán Cabello

Published May 2, 2025• 2 citations
arXivHTMLPDF

Abstract

Recent results show that Kochen-Specker (KS) sets of observables are fundamental to quantum information, computation, and foundations beyond previous expectations. Among KS sets, those that are unique up to unitary transformations (i.e., ``rigid'') are especially important. The problem is that we do not know any rigid KS set in ${\mathbb{C}}^{3}$, the smallest quantum system that allows for KS sets. Moreover, none of the existing methods for constructing KS sets leads to rigid KS sets in ${\mathbb{C}}^{3}$. Here, we show that two fundamental structures of quantum theory define two rigid KS sets. One of these structures is the supersymmetric informationally complete positive-operator-valued measure. The other is the minimal state-independent contextuality set. The second construction provides a clue to solve the minimal KS problem, the most important open problem in this field. We prove that there is no KS set of 30 elements that can be obtained from the minimal state-independent contextuality set by completing bases and adding elements that are orthogonal to two previous elements. We conjecture that 31 is the solution to the minimal KS set problem.

DOI
10.1103/physreva.111.052204

Related papers

On Simplest Kochen-Specker Sets

Mladen Pavicic

In Phys. Rev. Lett. 135, 190203 (2025) a discovery of the simplest 3D contextual set with 33 vertices, 50 bases, and 14 complete bases is claimed. In this paper, we show that it was previously generated in Quantum 7, 953 (2023) and analyze the meaning, origin, and significance of the simplest contextual sets in any dimension. In particular, we prove that there is no ground to consider the aforementioned set as fundamental since there are many 3D contextual sets with a smaller number of complete bases. We also show that automatic generation of contextual sets from basic vector components automatically yields all known minimal contextual sets of any kind in any dimension and therefore also the aforementioned set in no CPU-time. In the end, we discuss varieties of contextual sets, in particular Kochen-Specker (KS), extended KS, and non-KS sets as well as ambiguities in their definitions.

quant-pharXiv:2512.10483•Dec 12, 2025•0 citations

Minimal complexity of Kochen-Specker sets does not scale with dimension

Mordecai Waegell, P. K. Aravind

A Kochen-Specker (KS) set is a specific set of projectors and measurement contexts that prove the Bell-Kochen-Specker contextuality theorem. The simplest known KS sets in Hilbert space dimensions $d=3,4,5,6,8$ are reproduced, and several methods by which a new KS set can be constructed using one or more known KS sets in lower dimensions are reviewed and improved. These KS sets and improved methods enable the construction of explicitly critical new KS sets in all dimensions, where critical refers to the irreducibility of the set of contexts. The simplest known critical KS sets are derived in all even dimensions $d\ensuremath{\ge}10$ with at most nine contexts and 30 projectors, and in all odd dimensions $d\ensuremath{\ge}7$ with at most 13 contexts and 39 projectors. These results show that neither the number of contexts nor the number of projectors in a minimal KS set scales with dimension $d$.

arXiv:1702.05215•Physical Review A•May 2, 2017•9 citations

Optimal measurement structures for contextuality applications

Yuan Liu, Ravishankar Ramanathan, Karol Horodecki +2 more

Abstract The Kochen-Specker (KS) theorem is a corner-stone result in the foundations of quantum mechanics describing the fundamental difference between quantum theory and classical non-contextual theories. Recently specific substructures termed $01$-gadgets were shown to exist within KS proofs that capture the essential contradiction of the theorem. Here, we show these gadgets and their generalizations provide an optimal toolbox for contextuality applications including (i) constructing classical channels exhibiting entanglement-assisted advantage in zero-error communication, (ii) identifying large separations between quantum theory and binary generalised probabilistic theories, and (iii) finding optimal tests for contextuality-based semi-device-independent randomness generation. Furthermore, we introduce and study a generalisation to definite prediction sets for more general logical propositions, that we term higher-order gadgets. We pinpoint the role these higher-order gadgets play in KS proofs by identifying these as induced subgraphs within KS graphs and showing how to construct proofs of state-independent contextuality using higher-order gadgets as building blocks. The constructions developed here may help in solving some of the remaining open problems regarding minimal proofs of the Kochen-Specker theorem.

arXiv:2206.13139•npj Quantum Information•Jun 29, 2023•3 citations

Proving Kochen-Specker Theorem Using Projection Measurement and Positive Operator-Valued Measure

S. P. Toh

One of the main theorems on the impossibility of hidden variables in quantum mechanics is Kochen-Specker theorem (KS). This theorem says that any hidden variable theory that satisfies quantum mechanics must be contextual. More specifically, it asserts that, in Hilbert space of dimension ≥ 3, it is impossible to associate definite numerical values, 1 or 0, with every projection operator Pm, in such a way that, if a set of commuting Pm satisfies 1=ΣmP, the corresponding values will also satisfy . Since the first proof of Kochen and Specker using 117 vectors in R3, there were many attempts to reduce the number of vector either via conceiving ingenious models or extending the system being considered to higher dimension. By considering eight dimensional three qubits system, we found a state dependent proof that requires only five vectors. The state that we assign value of 1 is the ray that arises from intersection of two planes. The recent advancements show that the KS theorem proof can be extended to two dimensional quantum system through generalized measurement represented by positive operator-valued measured (POVM). In POVMs the number of available outcomes of a measurement may be higher than the dimensionality of the Hilbert space and N-outcome generalized measurement is represented by N-element POVM which consists of N positive semidefinite operators {}dE that sum to identity. Each pair of elements is not mutually orthogonal if the number of outcome of measurements is bigger than the dimensionality. In terms of POVM, Kochen-Specker theorem asserts that and could not be satisfied for . We developed a general model that enables us to generate different sizes of the POVM for the proof of the Kochen-Specker theorem. We show that the current simplest Nakamura model is in fact a special case of our model. W also provide another model which is as simple as the Nakamura’s but consists of different sets of POVM.

•Jan 1, 2008•0 citations

Simplest Kochen-Specker Set

Adán Cabello

Kochen-Specker (KS) sets are fundamental in physics. Every time nature produces bipartite correlations attaining the nonsignaling limit, or two parties always win a nonlocal game impossible to always win classically, it is because the parties are measuring a KS set. The simplest quantum system in which all these phenomena occur is a pair of three-level systems. However, the simplest KS sets known in dimension three are asymmetrical and require a large number of bases (the current minimum is 16, set by Peres and Penrose). Here, we present a KS set that is much more symmetrical and easier to prove than any previous example. It sets a new record for minimum number of bases, 14, and enables us to refute Conjecture 2 in Cabello Simplest bipartite perfect quantum strategies, Phys. Rev. Lett. 134, 010201 (2025)PRLTAO0031-900710.1103/PhysRevLett.134.010201, setting a new record for qutrit-qutrit perfect strategies with a minimum number of inputs: 5-9. We establish the fundamental nature of this set in quantum theory.

arXiv:2508.07335•Physical Review Letters•Nov 6, 2025•4 citations

Vector generation of contextual sets

Mladen Pavičić, Norman D. Megill

As quantum contextuality proves to be a necessary resource for universal quantum computation, we present a general method for vector generation of Kochen-Specker (KS) contextual sets in the form of hypergraphs. The method supersedes all three previous methods: (i) fortuitous discoveries of smallest KS sets, (ii) exhaustive upward hypergraph-generation of sets, and (iii) random downward generation of sets from fortuitously obtained big master sets. In contrast to previous works, we can generate master sets which contain all possible KS sets starting with nothing but a few simple vector components. From them we can readily generate all KS sets obtained in the last half a century and any specified new KS sets. Herewith we can generate sufficiently large sets as well as sets with definite required features and structures to enable varieties of different implementations in quantum computation and communication.

arXiv:1905.01784•EPJ Web of Conferences•Jan 1, 2019•3 citations
Recent results show that Kochen-Specker (KS) sets of observables are fundamental to quantum information, computation, and foundations beyond previous expectations. Among KS sets, those that are unique up to unitary transformations (i.e., ``rigid'') are especially important. The problem is that we do not know any rigid KS set in C3{\mathbb{C}}^{3}C3, the smallest quantum system that allows for KS sets. Moreover, none of the existing methods for constructing KS sets leads to rigid KS sets in C3{\mathbb{C}}^{3}C3. Here, we show that two fundamental structures of quantum theory define two rigid KS sets. One of these structures is the supersymmetric informationally complete positive-operator-valued measure. The other is the minimal state-independent contextuality set. The second construction provides a clue to solve the minimal KS problem, the most important open problem in this field. We prove that there is no KS set of 30 elements that can be obtained from the minimal state-independent contextuality set by completing bases and adding elements that are orthogonal to two previous elements. We conjecture that 31 is the solution to the minimal KS set problem.
In Phys. Rev. Lett. 135, 190203 (2025) a discovery of the simplest 3D contextual set with 33 vertices, 50 bases, and 14 complete bases is claimed. In this paper, we show that it was previously generated in Quantum 7, 953 (2023) and analyze the meaning, origin, and significance of the simplest contextual sets in any dimension. In particular, we prove that there is no ground to consider the aforementioned set as fundamental since there are many 3D contextual sets with a smaller number of complete bases. We also show that automatic generation of contextual sets from basic vector components automatically yields all known minimal contextual sets of any kind in any dimension and therefore also the aforementioned set in no CPU-time. In the end, we discuss varieties of contextual sets, in particular Kochen-Specker (KS), extended KS, and non-KS sets as well as ambiguities in their definitions.
A Kochen-Specker (KS) set is a specific set of projectors and measurement contexts that prove the Bell-Kochen-Specker contextuality theorem. The simplest known KS sets in Hilbert space dimensions d=3,4,5,6,8d=3,4,5,6,8d=3,4,5,6,8 are reproduced, and several methods by which a new KS set can be constructed using one or more known KS sets in lower dimensions are reviewed and improved. These KS sets and improved methods enable the construction of explicitly critical new KS sets in all dimensions, where critical refers to the irreducibility of the set of contexts. The simplest known critical KS sets are derived in all even dimensions $d\ensuremath{\ge}10$ with at most nine contexts and 30 projectors, and in all odd dimensions $d\ensuremath{\ge}7$ with at most 13 contexts and 39 projectors. These results show that neither the number of contexts nor the number of projectors in a minimal KS set scales with dimension ddd.
Abstract The Kochen-Specker (KS) theorem is a corner-stone result in the foundations of quantum mechanics describing the fundamental difference between quantum theory and classical non-contextual theories. Recently specific substructures termed 010101-gadgets were shown to exist within KS proofs that capture the essential contradiction of the theorem. Here, we show these gadgets and their generalizations provide an optimal toolbox for contextuality applications including (i) constructing classical channels exhibiting entanglement-assisted advantage in zero-error communication, (ii) identifying large separations between quantum theory and binary generalised probabilistic theories, and (iii) finding optimal tests for contextuality-based semi-device-independent randomness generation. Furthermore, we introduce and study a generalisation to definite prediction sets for more general logical propositions, that we term higher-order gadgets. We pinpoint the role these higher-order gadgets play in KS proofs by identifying these as induced subgraphs within KS graphs and showing how to construct proofs of state-independent contextuality using higher-order gadgets as building blocks. The constructions developed here may help in solving some of the remaining open problems regarding minimal proofs of the Kochen-Specker theorem.
One of the main theorems on the impossibility of hidden variables in quantum mechanics is Kochen-Specker theorem (KS). This theorem says that any hidden variable theory that satisfies quantum mechanics must be contextual. More specifically, it asserts that, in Hilbert space of dimension ≥ 3, it is impossible to associate definite numerical values, 1 or 0, with every projection operator Pm, in such a way that, if a set of commuting Pm satisfies 1=ΣmP, the corresponding values will also satisfy . Since the first proof of Kochen and Specker using 117 vectors in R3, there were many attempts to reduce the number of vector either via conceiving ingenious models or extending the system being considered to higher dimension. By considering eight dimensional three qubits system, we found a state dependent proof that requires only five vectors. The state that we assign value of 1 is the ray that arises from intersection of two planes. The recent advancements show that the KS theorem proof can be extended to two dimensional quantum system through generalized measurement represented by positive operator-valued measured (POVM). In POVMs the number of available outcomes of a measurement may be higher than the dimensionality of the Hilbert space and N-outcome generalized measurement is represented by N-element POVM which consists of N positive semidefinite operators {}dE that sum to identity. Each pair of elements is not mutually orthogonal if the number of outcome of measurements is bigger than the dimensionality. In terms of POVM, Kochen-Specker theorem asserts that and could not be satisfied for . We developed a general model that enables us to generate different sizes of the POVM for the proof of the Kochen-Specker theorem. We show that the current simplest Nakamura model is in fact a special case of our model. W also provide another model which is as simple as the Nakamura’s but consists of different sets of POVM.
Kochen-Specker (KS) sets are fundamental in physics. Every time nature produces bipartite correlations attaining the nonsignaling limit, or two parties always win a nonlocal game impossible to always win classically, it is because the parties are measuring a KS set. The simplest quantum system in which all these phenomena occur is a pair of three-level systems. However, the simplest KS sets known in dimension three are asymmetrical and require a large number of bases (the current minimum is 16, set by Peres and Penrose). Here, we present a KS set that is much more symmetrical and easier to prove than any previous example. It sets a new record for minimum number of bases, 14, and enables us to refute Conjecture 2 in Cabello Simplest bipartite perfect quantum strategies, Phys. Rev. Lett. 134, 010201 (2025)PRLTAO0031-900710.1103/PhysRevLett.134.010201, setting a new record for qutrit-qutrit perfect strategies with a minimum number of inputs: 5-9. We establish the fundamental nature of this set in quantum theory.
As quantum contextuality proves to be a necessary resource for universal quantum computation, we present a general method for vector generation of Kochen-Specker (KS) contextual sets in the form of hypergraphs. The method supersedes all three previous methods: (i) fortuitous discoveries of smallest KS sets, (ii) exhaustive upward hypergraph-generation of sets, and (iii) random downward generation of sets from fortuitously obtained big master sets. In contrast to previous works, we can generate master sets which contain all possible KS sets starting with nothing but a few simple vector components. From them we can readily generate all KS sets obtained in the last half a century and any specified new KS sets. Herewith we can generate sufficiently large sets as well as sets with definite required features and structures to enable varieties of different implementations in quantum computation and communication.