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

SAT + NAUTY: Orderly Generation of Small Kochen-Specker Sets Containing the Smallest State-independent Contextuality Set

Zhengyu Li, Curtis Bright, Stefan Trandafir, Adán Cabello, Vijay Ganesh

cs.LOmath.COquant-phSubmitted Apr 21, 2026• Announced Apr 23, 2026• 0 citations
arXivHTMLPDF

Abstract

We present a search for small Kochen-Specker (KS) sets in dimension 3, specifically targeting extensions of the 13-ray Yu-Oh set, which has been proven to be the minimal witness to state-independent contextuality. To enable this search, we introduce a novel SAT-based orderly generation framework integrating recursive canonical labeling (RCL) with the graph isomorphism tool NAUTY. We demonstrate that previous SAT approaches relying on lexicographical canonicity suffer from exponential scaling on canonical graphs. This limitation renders them intractable on the large instances (25 to 33 vertices) encountered in our search, whereas our RCL check maintains consistent millisecond-level performance, effectively eliminating the bottleneck. Overcoming this bottleneck allows us to perform the first exhaustive enumeration of all KS sets with up to 33 rays containing the complete 25-ray state-independent contextuality (SI-C) set obtained by rigid extensions of the Yu-Oh set in 1,641 CPU hours. We found and verified that the 33-ray set discovered by Schütte is the smallest three-dimensional KS set containing the complete 25-ray SI-C set. All non-existence results are backed by independently verifiable proof certificates via an extension of the DRAT proof format.

Related papers

A SAT Solver + Computer Algebra Attack on the Minimum Kochen–Specker Problem

Zhengyu Li, Curtis Bright, Vijay Ganesh

One of the fundamental results in quantum foundations is the Kochen–Specker (KS) theorem, which states that any theory whose predictions agree with quantum mechanics must be contextual, i.e., a quantum observation cannot be understood as revealing a pre-existing value. The theorem hinges on the existence of a mathematical object called a KS vector system. While many KS vector systems are known, the problem of finding the minimum KS vector system in three dimensions (3D) has remained stubbornly open for over 55 years. To address the minimum KS problem, we present a new verifiable proof-producing method based on a combination of a Boolean satisfiability (SAT) solver and a computer algebra system (CAS) that uses an isomorph-free orderly generation technique that is very effective in pruning away large parts of the search space. Our method shows that a KS system in 3D must contain at least 24 vectors. We show that our sequential and parallel Cube-and-Conquer (CnC) SAT+CAS methods are significantly faster than SAT-only, CAS-only, and a prior CAS-based method of Uijlen and Westerbaan. Further, while our parallel pipeline is somewhat slower than the parallel CnC version of the recently introduced Satisfiability Modulo Theories (SMS) method, this is in part due to the overhead of proof generation. Finally, we provide the first computer-verifiable proof certificate of a lower bound to the KS problem with a size of 40.3 TiB in order 23.

arXiv:2306.13319•International Joint Conference on Artificial Intelligence•Jul 26, 2024•12 citations

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

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

Quantum state-independent contextuality requires 13 rays

Adán Cabello, Matthias Kleinmann, José R. Portillo

Abstract We show that, regardless of the dimension of the Hilbert space, there exists no set of rays revealing state-independent contextuality with less than 13 rays. This implies that the set proposed by Yu and Oh in dimension three (2012 Phys. Rev. Lett. 108 030402 ) is actually the minimal set in quantum theory. This contrasts with the case of Kochen–Specker sets, where the smallest set occurs in dimension four.

arXiv:1606.01848•Journal of Physics A Mathematical and Theoretical•Aug 30, 2016•52 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•4 citations

Construction of Kochen–Specker Sets from Mutually Unbiased Bases

Mirko Navara, Karl Svozil

We give a constructive analysis of Kochen-Specker (KS) contextuality at the level of complete orthogonal bases (contexts). In dimension three, three noncomputational mutually unbiased bases generate a union of 165 rays and 130 contexts. Exact provenance accounting gives a symmetric decomposition: the three 69-ray lineages share 21 rays and 10 contexts, while each contributes 48 exclusive rays and 40 lineage-specific contexts. Each 69-ray, 50-context lineage is a KS configuration, and this framework clarifies the relation among the Yu-Oh, Harding-Salinas Schmeis, and Cabello constructions. In dimensions four and five, we give parametrized orthogonality gadgets whose connector contexts force a central ray to be maximally unbiased relative to the computational basis. For the concrete four-dimensional example, the 20-ray gadget and the Cabello 18-ray set are informationally equivalent subsets of the 24-ray Peres-Mermin eigensystem, although their context hypergraphs have different two-valued-state behavior. The results show why both the rays and the complete incidence structure of their contexts are needed in assessments of KS contextuality.

arXiv:2509.08636•International Journal of Theoretical Physics•Nov 12, 2026•4 citations
We present a search for small Kochen-Specker (KS) sets in dimension 3, specifically targeting extensions of the 13-ray Yu-Oh set, which has been proven to be the minimal witness to state-independent contextuality. To enable this search, we introduce a novel SAT-based orderly generation framework integrating recursive canonical labeling (RCL) with the graph isomorphism tool NAUTY. We demonstrate that previous SAT approaches relying on lexicographical canonicity suffer from exponential scaling on canonical graphs. This limitation renders them intractable on the large instances (25 to 33 vertices) encountered in our search, whereas our RCL check maintains consistent millisecond-level performance, effectively eliminating the bottleneck. Overcoming this bottleneck allows us to perform the first exhaustive enumeration of all KS sets with up to 33 rays containing the complete 25-ray state-independent contextuality (SI-C) set obtained by rigid extensions of the Yu-Oh set in 1,641 CPU hours. We found and verified that the 33-ray set discovered by Schütte is the smallest three-dimensional KS set containing the complete 25-ray SI-C set. All non-existence results are backed by independently verifiable proof certificates via an extension of the DRAT proof format.
One of the fundamental results in quantum foundations is the Kochen–Specker (KS) theorem, which states that any theory whose predictions agree with quantum mechanics must be contextual, i.e., a quantum observation cannot be understood as revealing a pre-existing value. The theorem hinges on the existence of a mathematical object called a KS vector system. While many KS vector systems are known, the problem of finding the minimum KS vector system in three dimensions (3D) has remained stubbornly open for over 55 years. To address the minimum KS problem, we present a new verifiable proof-producing method based on a combination of a Boolean satisfiability (SAT) solver and a computer algebra system (CAS) that uses an isomorph-free orderly generation technique that is very effective in pruning away large parts of the search space. Our method shows that a KS system in 3D must contain at least 24 vectors. We show that our sequential and parallel Cube-and-Conquer (CnC) SAT+CAS methods are significantly faster than SAT-only, CAS-only, and a prior CAS-based method of Uijlen and Westerbaan. Further, while our parallel pipeline is somewhat slower than the parallel CnC version of the recently introduced Satisfiability Modulo Theories (SMS) method, this is in part due to the overhead of proof generation. Finally, we provide the first computer-verifiable proof certificate of a lower bound to the KS problem with a size of 40.3 TiB in order 23.
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.
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.
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.
We give a constructive analysis of Kochen-Specker (KS) contextuality at the level of complete orthogonal bases (contexts). In dimension three, three noncomputational mutually unbiased bases generate a union of 165 rays and 130 contexts. Exact provenance accounting gives a symmetric decomposition: the three 69-ray lineages share 21 rays and 10 contexts, while each contributes 48 exclusive rays and 40 lineage-specific contexts. Each 69-ray, 50-context lineage is a KS configuration, and this framework clarifies the relation among the Yu-Oh, Harding-Salinas Schmeis, and Cabello constructions. In dimensions four and five, we give parametrized orthogonality gadgets whose connector contexts force a central ray to be maximally unbiased relative to the computational basis. For the concrete four-dimensional example, the 20-ray gadget and the Cabello 18-ray set are informationally equivalent subsets of the 24-ray Peres-Mermin eigensystem, although their context hypergraphs have different two-valued-state behavior. The results show why both the rays and the complete incidence structure of their contexts are needed in assessments of KS contextuality.