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

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

Mordecai Waegell, P. K. Aravind

Published May 2, 2017• 11 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.1103/physreva.95.050101

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•1 citation

Kochen-Specker set with seven contexts

Petr Lisoněk, Piotr Badziąg, José R. Portillo +1 more

The Kochen-Specker (KS) theorem is a central result in quantum theory and has applications in quantum information. Its proof requires several yes-no tests that can be grouped in contexts or subsets of jointly measurable tests. Arguably, the best measure of simplicity of a KS set is the number of contexts. The smaller this number is, the smaller the number of experiments needed to reveal the conflict between quantum theory and noncontextual theories and to get a quantum vs classical outperformance. The original KS set had 132 contexts. Here we introduce a KS set with seven contexts and prove that this is the simplest KS set that admits a symmetric parity proof.

arXiv:1308.6012•Physical Review A•Apr 1, 2014•59 citations

Generation of Kochen-Specker contextual sets in higher dimensions by dimensional upscaling whose complexity does not scale with dimension and their applications

Mladen Pavičić, Mordecai Waegell

Recently, handling of contextual sets, in particular Kochen-Specker (KS) sets, in higher dimensions has been given an increasing attention, both theoretically and experimentally. However, methods of their generation are diverse, not generally applicable in every dimension, and of exponential complexity. Therefore, we design a dimensional upscaling method, whose complexity does not scale with dimension. As a proof of principle we generate manageable-sized KS master sets in up to 27 dimensional spaces and show that well over 32 dimensions can be reached. From these master sets we obtain an ample number of smaller KS sets. We discuss three kinds of applications that work with KS sets in higher dimensions. We anticipate other applications of KS sets for quantum information processing that make use of large families of nonisomorphic KS sets.

arXiv:2305.08267•Physical Review A•Jul 3, 2024•5 citations

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

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.

arXiv:2501.11640•Physical Review A•May 2, 2025•3 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•12 citations

Emergence and Recovery of (logical) Kochen-Specker Contextuality via Hamilton Extension

Jayashree Karmakar, Biswadeep Chatterjee, Rafiuddin Gazi +5 more

Logical Kochen-Specker (KS) contextuality is widely regarded as an intrinsic property of specially constructed measurement configurations. We show instead that it can emerge from KS-colorable vector sets through a constructive procedure we call the Hamilton extension. Defined for four-dimensional vector sets, the Hamilton extension associates each real vector with a measurement context while inducing additional measurement contexts among Hamilton-extended children of distinct parent vectors. These emergent contexts fundamentally alter the compatibility structure, transforming KS-colorable configurations into KS-uncolorable ones and recovering logical contextuality lost under apex-vertex augmentation. We establish a sharp and optimal threshold -- the Hamilton extension of every five-vector parent set remains KS-colorable, whereas suitably chosen six-vector parent sets already generate logical KS contradictions. Thus, six vectors constitute the smallest parent set capable of generating KS contradiction through this mechanism. Our results reveal a new structural route to contextuality, provide a systematic framework for constructing compact KS sets, and have implications for contextuality-based quantum information protocols and graph-theoretic approaches to nonclassicality.

quant-pharXiv:2607.14629•Jul 17, 2026•0 citations
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≥10d\ensuremath{\ge}10d\ensuremath≥10 with at most nine contexts and 30 projectors, and in all odd dimensions d\ensuremath≥7d\ensuremath{\ge}7d\ensuremath≥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.
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.
The Kochen-Specker (KS) theorem is a central result in quantum theory and has applications in quantum information. Its proof requires several yes-no tests that can be grouped in contexts or subsets of jointly measurable tests. Arguably, the best measure of simplicity of a KS set is the number of contexts. The smaller this number is, the smaller the number of experiments needed to reveal the conflict between quantum theory and noncontextual theories and to get a quantum vs classical outperformance. The original KS set had 132 contexts. Here we introduce a KS set with seven contexts and prove that this is the simplest KS set that admits a symmetric parity proof.
Recently, handling of contextual sets, in particular Kochen-Specker (KS) sets, in higher dimensions has been given an increasing attention, both theoretically and experimentally. However, methods of their generation are diverse, not generally applicable in every dimension, and of exponential complexity. Therefore, we design a dimensional upscaling method, whose complexity does not scale with dimension. As a proof of principle we generate manageable-sized KS master sets in up to 27 dimensional spaces and show that well over 32 dimensions can be reached. From these master sets we obtain an ample number of smaller KS sets. We discuss three kinds of applications that work with KS sets in higher dimensions. We anticipate other applications of KS sets for quantum information processing that make use of large families of nonisomorphic KS sets.
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.
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.
Logical Kochen-Specker (KS) contextuality is widely regarded as an intrinsic property of specially constructed measurement configurations. We show instead that it can emerge from KS-colorable vector sets through a constructive procedure we call the Hamilton extension. Defined for four-dimensional vector sets, the Hamilton extension associates each real vector with a measurement context while inducing additional measurement contexts among Hamilton-extended children of distinct parent vectors. These emergent contexts fundamentally alter the compatibility structure, transforming KS-colorable configurations into KS-uncolorable ones and recovering logical contextuality lost under apex-vertex augmentation. We establish a sharp and optimal threshold -- the Hamilton extension of every five-vector parent set remains KS-colorable, whereas suitably chosen six-vector parent sets already generate logical KS contradictions. Thus, six vectors constitute the smallest parent set capable of generating KS contradiction through this mechanism. Our results reveal a new structural route to contextuality, provide a systematic framework for constructing compact KS sets, and have implications for contextuality-based quantum information protocols and graph-theoretic approaches to nonclassicality.