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

An obstruction based approach to the Kochen-Specker theorem

J. Hamilton

Published Jan 1, 1999• 2 citations
OpenAlex

Abstract

In [1] it was shown that the Kochen Specker theorem can be written in terms of the non-existence of global elements of a certain varying set over the category W of boolean subalgebras of projection operators on some Hilbert space H. In this paper, we show how obstructions to the construction of such global elements arise, and how this provides a new way of looking at proofs of the theorem.

Related papers

An obstruction-based approach to the Kochen-Specker theorem

J Hamilton

In Isham and Butterfield (1998 Int. J. Theor. Phys. 37 2669-733) it was shown that the Kochen-Specker theorem can be written in terms of the non-existence of global elements of a certain varying set over the category of Boolean subalgebras of projection operators on some Hilbert space . In this paper, we show how obstructions to the construction of such global elements arise, and how this provides a new way of looking at proofs of the theorem.

arXiv:quant-ph/9912018•Journal of Physics A Mathematical and General•May 11, 2000•3 citations

Bell - Kochen - Specker theorem for any finite dimension

Adán Cabello, Guillermo García Alcaine

The Bell - Kochen - Specker theorem against non-contextual hidden variables can be proved by constructing a finite set of `totally non-colourable' directions, as Kochen and Specker did in a Hilbert space of dimension n = 3. We generalize Kochen and Specker's set to Hilbert spaces of any finite dimension , in a three-step process that shows the relationship between different kinds of proofs (`continuum', `probabilistic', `state-specific' and `state-independent') of the Bell - Kochen - Specker theorem. At the same time, this construction of a totally non-colourable set of directions in any dimension explicitly solves the question raised by Zimba and Penrose about the existence of such a set for n = 5.

Journal of Physics A Mathematical and General•Mar 7, 1996•45 citations

How orthogonalities set Kochen-Specker sets

Kate Blanchfield

We look at generalisations of sets of vectors proving the Kochen-Specker theorem in 3 and 4 dimensions. It has been shown that two such sets, although unitarily inequivalent, are part of a larger 3-parameter family of vectors that share the same orthogonality graph. We find that these sets are unusual, in that the vectors in all other Kochen-Specker sets investigated here are fully determined by orthog-onality conditions and thus admit no free parameters. The Kochen-Specker (KS) theorem [1] is a statement about the fundamen-tal nature of quantum mechanics: no non-contextual hidden variable theory can reliably reproduce quantum mechanical predictions. The KS theorem states that in a Hilbert space with dimension n ≥ 3 it is impossible to assign definite values v ∈ {0, 1} to m projection operators Pm so that for every commuting set of projection operators satisfying Pm = I, the correspond-ing definite values obey v (Pm) = 1. The KS theorem is often visualised by means of a set of "uncolourable" vectors, where projection operators are represented by their constituent rays in Hilbert space and rays can be simplified to vectors as only directions are relevant here. The vectors are coloured according to their pre-assigned val-ues and the summation conditions above translate into colouring rules. This allows us to construct orthogonality graphs that, when uncolourable, pro-vide a contradiction within non-contextual hidden variable models and thus a proof of the KS theorem. Sets of vectors exemplifying the KS theorem have been discovered by nu-merous authors, with an aim to reduce the number of vectors required to reach a contradiction. Most notably, in a 3-dimensional Hilbert space, the original KS proof of 117 vectors has been replicated with sets using between 31 and 33 vectors [2, 3, 4, 5] and in a 4-dimensional Hilbert space, sets of between 24 and the lower limit of 18 vectors have been realised [2, 6, 7]. Additionally, an extensive computer search has recently revealed over one thousand of such KS sets in R4 [8]. In a publication by E. Gould and P. K. Aravind [10], two of these sets in 3 dimensions have been shown to share the same orthogonality graph. Specifically, the sets of 33 vectors found by Penrose [3] and Peres [2] have

•Aug 14, 2016•1 citation

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

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

Leibniz international proceedings in informatics•Jan 1, 2026•0 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
In [1] it was shown that the Kochen Specker theorem can be written in terms of the non-existence of global elements of a certain varying set over the category W of boolean subalgebras of projection operators on some Hilbert space H. In this paper, we show how obstructions to the construction of such global elements arise, and how this provides a new way of looking at proofs of the theorem.
The Bell - Kochen - Specker theorem against non-contextual hidden variables can be proved by constructing a finite set of `totally non-colourable' directions, as Kochen and Specker did in a Hilbert space of dimension n = 3. We generalize Kochen and Specker's set to Hilbert spaces of any finite dimension , in a three-step process that shows the relationship between different kinds of proofs (`continuum', `probabilistic', `state-specific' and `state-independent') of the Bell - Kochen - Specker theorem. At the same time, this construction of a totally non-colourable set of directions in any dimension explicitly solves the question raised by Zimba and Penrose about the existence of such a set for n = 5.
We look at generalisations of sets of vectors proving the Kochen-Specker theorem in 3 and 4 dimensions. It has been shown that two such sets, although unitarily inequivalent, are part of a larger 3-parameter family of vectors that share the same orthogonality graph. We find that these sets are unusual, in that the vectors in all other Kochen-Specker sets investigated here are fully determined by orthog-onality conditions and thus admit no free parameters. The Kochen-Specker (KS) theorem [1] is a statement about the fundamen-tal nature of quantum mechanics: no non-contextual hidden variable theory can reliably reproduce quantum mechanical predictions. The KS theorem states that in a Hilbert space with dimension n ≥ 3 it is impossible to assign definite values v ∈ {0, 1} to m projection operators Pm so that for every commuting set of projection operators satisfying Pm = I, the correspond-ing definite values obey v (Pm) = 1. The KS theorem is often visualised by means of a set of "uncolourable" vectors, where projection operators are represented by their constituent rays in Hilbert space and rays can be simplified to vectors as only directions are relevant here. The vectors are coloured according to their pre-assigned val-ues and the summation conditions above translate into colouring rules. This allows us to construct orthogonality graphs that, when uncolourable, pro-vide a contradiction within non-contextual hidden variable models and thus a proof of the KS theorem. Sets of vectors exemplifying the KS theorem have been discovered by nu-merous authors, with an aim to reduce the number of vectors required to reach a contradiction. Most notably, in a 3-dimensional Hilbert space, the original KS proof of 117 vectors has been replicated with sets using between 31 and 33 vectors [2, 3, 4, 5] and in a 4-dimensional Hilbert space, sets of between 24 and the lower limit of 18 vectors have been realised [2, 6, 7]. Additionally, an extensive computer search has recently revealed over one thousand of such KS sets in R4 [8]. In a publication by E. Gould and P. K. Aravind [10], two of these sets in 3 dimensions have been shown to share the same orthogonality graph. Specifically, the sets of 33 vectors found by Penrose [3] and Peres [2] have
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.
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 satisfiability 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 satisfiability 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.
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.