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:2211.13216 · Journal of Algebra and Its Applications

Minimal ring extensions of the integers exhibiting Kochen–Specker contextuality

Ida Cortez, Camilo Morales, Manuel L. Reyes

Published Oct 31, 2025• 0 citations
arXivHTMLPDF

Abstract

This paper is a contribution to the algebraic study of contextuality in quantum theory. As an algebraic analogue of Kochen and Specker’s no-hidden-variables result, we investigate rational subrings over which the partial ring of [Formula: see text] symmetric matrices ([Formula: see text]) admits no morphism to a nonzero commutative ring, which we view as an “algebraic hidden state”. For [Formula: see text], the minimal such ring is shown to be [Formula: see text], while for [Formula: see text] the minimal subring is [Formula: see text] itself. The proofs rely on the construction of new sets of integer vectors in dimensions 3 and 6 that have no Kochen–Specker coloring.

DOI
10.1142/s0219498825420174

Related papers

Algebraic partial Boolean algebras

D. A. Smith

Partial Boolean algebras, first studied by Kochen and Specker in the 1960s, provide the structure for Bell–Kochen–Specker theorems which deny the existence of non-contextual hidden variable theories. In this paper, we study partial Boolean algebras which are ‘algebraic’ in the sense that their elements have coordinates in an algebraic number field. Several of these algebras have been discussed recently in a debate on the validity of Bell–Kochen–Specker theorems in the context of finite precision measurements. The main result of this paper is that every algebraic finitely-generated partial Boolean algebra B ( T ) is finite when the underlying space ℋ is three-dimensional, answering a question of Kochen and showing that Conway and Kochen's infinite algebraic partial Boolean algebra has minimum dimension. This result contrasts the existence of an infinite (non-algebraic) B ( T ) generated by eight elements in an abstract orthomodular lattice of height 3. We then initiate a study of higher-dimensional algebraic partial Boolean algebras. First, we describe a restriction on the determinants of the elements of B ( T ) that are generated by a given set T . We then show that when the generating set T consists of the rays spanning the minimal vectors in a real irreducible root lattice, B ( T ) is infinite just if that root lattice has an A 5 sublattice. Finally, we characterize the rays of B ( T ) when T consists of the rays spanning the minimal vectors of the root lattice E 8 .

Journal of Physics A Mathematical and General•Mar 19, 2003•5 citations

Minimal Kochen-Specker theorem in finite dimensions

Sixia Yu, C. H. Oh

In [1] we proved a strengthened Kochen-Specker theorem in 3 dimensions: non-contextual hidden variable (NCHV) models cannot reproduce all the quantum correlations of two compatible observables, which is a minimal requirement imposed on the NCHV models. Here we shall exclude the NCHV models with this minimal requirement in $d\ge 4$ dimensions by state-independent and experimentally testable inequalities satisfied by all NCHV models that are required to reproduce only the quantum correlations of at most two compatible observables. Furthermore our proofs use the smallest number of rays known so far, e.g., 25 (instead of 31) rays in $5$ dimensions and $5d-2\lfloor d/3\rfloor$ rays in $d\ge 6$ dimensions.

arXiv:1112.5513•Dec 23, 2011•2 citations

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

Zhengyu Li, Curtis Bright, Vijay Ganesh

Abstract One of the most fundamental results in the foundations of quantum mechanics is the Kochen--Specker (KS) theorem, a `no-go' theorem which states that contextuality is an essential feature of any hidden-variable theory. The theorem hinges on the existence of a mathematical object called a KS vector system. Although the existence of a KS vector system was first established by Kochen and Specker, the problem of the minimum size of such a system has stubbornly remained open for over 50 years. In this paper, we present a new method based on a combination of a SAT solver and a computer algebra system (CAS) to address this problem. We improve the lower bound on the minimum number of vectors in a KS system from 22 to 23 and improve the efficiency of the search by a factor of over 1000 when compared to the most recent computational methods. Finding a minimum KS system would simplify experimental tests of the KS theorem and have direct applications in quantum information processing, specifically in the security of quantum cryptographic protocols based on complementarity, zero-error classical communication, and dimension witnessing.

•Jun 21, 2023•2 citations

Construction of state-independent proofs for quantum contextuality

Weidong Tang, Sixia Yu

Since the enlightening proofs of quantum contextuality first established by Kochen and Specker, and also by Bell, various simplified proofs have been constructed to exclude the noncontextual hidden variable theory of our nature at the microscopic scale. The conflict between the noncontextual hidden variable theory and quantum mechanics is commonly revealed by Kochen-Specker sets of yes-no tests, represented by projectors (or rays), via either logical contradictions or noncontextuality inequalities in a state-(in)dependent manner. Here we propose a systematic and programmable construction of a state-independent proof from a given set of nonspecific rays in ${\mathbb{C}}^{3}$ according to their Gram matrix. This approach brings us a greater convenience in the experimental arrangements. Besides, our proofs in ${\mathbb{C}}^{3}$ can also be generalized to any higher-dimensional systems by a recursive method.

arXiv:1707.05626•Physical Review A•Dec 21, 2017•5 citations

Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras

Anuj Dawar, Nihil Shah

The Kochen-Specker no-go theorem established that hidden-variable theories in quantum mechanics necessarily admit contextuality. This theorem is formally stated in terms of the partial Boolean algebra structure of projectors on a Hilbert space. Each partial Boolean algebra provides a semantics for interpreting propositional logic. In this paper, we examine the complexity of propositional satisfiablity for various classes of partial Boolean algebras. We first show that the satisfiability problem for the class of non-trivial partial Boolean algebras is NP-complete. Next, we consider the satisfiability problem for the class of partial Boolean algebras arising from projectors on finite dimensional Hilbert spaces. For real Hilbert spaces of dimension greater 2 and any complex Hilbert spaces of dimension greater than 3, we demonstrate that the satisfiablity problem is complete for the existential theory of the reals. Interestingly, the proofs of these results make use of Kochen-Specker sets as gadgets. As a corollary, we conclude that deciding quantum homomorphism in these fixed dimensions are also complete for the existential theory of the reals. Finally, we show that the satisfiability problems for the class of all Hilbert spaces and all finite-dimensional Hilbert spaces is undecidable.

quant-pharXiv:2602.24164•Mar 2, 2026•0 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
This paper is a contribution to the algebraic study of contextuality in quantum theory. As an algebraic analogue of Kochen and Specker’s no-hidden-variables result, we investigate rational subrings over which the partial ring of [Formula: see text] symmetric matrices ([Formula: see text]) admits no morphism to a nonzero commutative ring, which we view as an “algebraic hidden state”. For [Formula: see text], the minimal such ring is shown to be [Formula: see text], while for [Formula: see text] the minimal subring is [Formula: see text] itself. The proofs rely on the construction of new sets of integer vectors in dimensions 3 and 6 that have no Kochen–Specker coloring.
Partial Boolean algebras, first studied by Kochen and Specker in the 1960s, provide the structure for Bell–Kochen–Specker theorems which deny the existence of non-contextual hidden variable theories. In this paper, we study partial Boolean algebras which are ‘algebraic’ in the sense that their elements have coordinates in an algebraic number field. Several of these algebras have been discussed recently in a debate on the validity of Bell–Kochen–Specker theorems in the context of finite precision measurements. The main result of this paper is that every algebraic finitely-generated partial Boolean algebra B ( T ) is finite when the underlying space ℋ is three-dimensional, answering a question of Kochen and showing that Conway and Kochen's infinite algebraic partial Boolean algebra has minimum dimension. This result contrasts the existence of an infinite (non-algebraic) B ( T ) generated by eight elements in an abstract orthomodular lattice of height 3. We then initiate a study of higher-dimensional algebraic partial Boolean algebras. First, we describe a restriction on the determinants of the elements of B ( T ) that are generated by a given set T . We then show that when the generating set T consists of the rays spanning the minimal vectors in a real irreducible root lattice, B ( T ) is infinite just if that root lattice has an A 5 sublattice. Finally, we characterize the rays of B ( T ) when T consists of the rays spanning the minimal vectors of the root lattice E 8 .
In [1] we proved a strengthened Kochen-Specker theorem in 3 dimensions: non-contextual hidden variable (NCHV) models cannot reproduce all the quantum correlations of two compatible observables, which is a minimal requirement imposed on the NCHV models. Here we shall exclude the NCHV models with this minimal requirement in d≥4d\ge 4d≥4 dimensions by state-independent and experimentally testable inequalities satisfied by all NCHV models that are required to reproduce only the quantum correlations of at most two compatible observables. Furthermore our proofs use the smallest number of rays known so far, e.g., 25 (instead of 31) rays in 555 dimensions and 5d−2⌊d/3⌋5d-2\lfloor d/3\rfloor5d−2⌊d/3⌋ rays in d≥6d\ge 6d≥6 dimensions.
Abstract One of the most fundamental results in the foundations of quantum mechanics is the Kochen--Specker (KS) theorem, a `no-go' theorem which states that contextuality is an essential feature of any hidden-variable theory. The theorem hinges on the existence of a mathematical object called a KS vector system. Although the existence of a KS vector system was first established by Kochen and Specker, the problem of the minimum size of such a system has stubbornly remained open for over 50 years. In this paper, we present a new method based on a combination of a SAT solver and a computer algebra system (CAS) to address this problem. We improve the lower bound on the minimum number of vectors in a KS system from 22 to 23 and improve the efficiency of the search by a factor of over 1000 when compared to the most recent computational methods. Finding a minimum KS system would simplify experimental tests of the KS theorem and have direct applications in quantum information processing, specifically in the security of quantum cryptographic protocols based on complementarity, zero-error classical communication, and dimension witnessing.
Since the enlightening proofs of quantum contextuality first established by Kochen and Specker, and also by Bell, various simplified proofs have been constructed to exclude the noncontextual hidden variable theory of our nature at the microscopic scale. The conflict between the noncontextual hidden variable theory and quantum mechanics is commonly revealed by Kochen-Specker sets of yes-no tests, represented by projectors (or rays), via either logical contradictions or noncontextuality inequalities in a state-(in)dependent manner. Here we propose a systematic and programmable construction of a state-independent proof from a given set of nonspecific rays in C3{\mathbb{C}}^{3}C3 according to their Gram matrix. This approach brings us a greater convenience in the experimental arrangements. Besides, our proofs in C3{\mathbb{C}}^{3}C3 can also be generalized to any higher-dimensional systems by a recursive method.
The Kochen-Specker no-go theorem established that hidden-variable theories in quantum mechanics necessarily admit contextuality. This theorem is formally stated in terms of the partial Boolean algebra structure of projectors on a Hilbert space. Each partial Boolean algebra provides a semantics for interpreting propositional logic. In this paper, we examine the complexity of propositional satisfiablity for various classes of partial Boolean algebras. We first show that the satisfiability problem for the class of non-trivial partial Boolean algebras is NP-complete. Next, we consider the satisfiability problem for the class of partial Boolean algebras arising from projectors on finite dimensional Hilbert spaces. For real Hilbert spaces of dimension greater 2 and any complex Hilbert spaces of dimension greater than 3, we demonstrate that the satisfiablity problem is complete for the existential theory of the reals. Interestingly, the proofs of these results make use of Kochen-Specker sets as gadgets. As a corollary, we conclude that deciding quantum homomorphism in these fixed dimensions are also complete for the existential theory of the reals. Finally, we show that the satisfiability problems for the class of all Hilbert spaces and all finite-dimensional Hilbert spaces is undecidable.
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.