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:1010.4662 · Journal of Mathematical Physics

The extension problem for partial Boolean structures in quantum mechanics

Costantino Budroni, G. Morchio

Published Dec 1, 2010• 18 citations
arXivHTMLPDF

Abstract

Alternative partial Boolean structures, implicit in the discussion of classical representability of sets of quantum mechanical predictions, are characterized, with definite general conclusions on the equivalence of the approaches going back to Bell and Kochen–Specker. An algebraic approach is presented, allowing for a discussion of partial classical extension, amounting to reduction of the “number of contexts,” classical representability arising as a special case. As a result, known techniques are generalized and some of the associated computational difficulties overcome. The implications on the discussion of Boole–Bell inequalities are indicated.

DOI
10.1063/1.3523478

Related papers

The Logic of Contextuality

Samson Abramsky, Rui Soares Barbosa

Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.

arXiv:2011.03064•Leibniz international proceedings in informatics•Nov 5, 2020•8 citations

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

Logical Structures Arising in Quantum Theory

Simon Kochen, Ernst P. Specker

The logical structures studied in this paper are generalizations of the propositional calculus. The classical propositional calculus is essentially Boolean algebra or, alternatively, the theory of functions on an arbitrary set S with values in a two-element set. The generalization consists in allowing partial functions on the set S , i.e., functions defined on certain subsets of S , and defining an equivalence relation among these functions such that any two constant functions with the same constant value belong to the same equivalence class. The generalization is equally natural for functions with values in the field of real numbers and we shall consider this case first. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Birkhäuser Basel eBooks•Jan 1, 1990•82 citations

Partial quantum logics revisited

Thomas Vetterlein

Partial Boolean algebras (PBAs) were introduced by Kochen and Specker as an algebraic model reflecting the mutual relationships among quantum-physical yes–no tests. The fact that not all pairs of tests are compatible was taken into special account. In this paper, we review PBAs from two sides. First, we generalise the concept, taking into account also those yes–no tests which are based on unsharp measurements. Namely, we introduce partial MV-algebras, and we define a corresponding logic. Second, we turn to the representation theory of PBAs. In analogy to the case of orthomodular lattices, we give conditions for a PBA to be isomorphic to the PBA of closed subspaces of a complex Hilbert space. Hereby, we do not restrict ourselves to purely algebraic statements; we rather give preference to conditions involving automorphisms of a PBA. We conclude by outlining a critical view on the logico-algebraic approach to the foundational problem of quantum physics.

International Journal of General Systems•Jul 21, 2010•4 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

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
Alternative partial Boolean structures, implicit in the discussion of classical representability of sets of quantum mechanical predictions, are characterized, with definite general conclusions on the equivalence of the approaches going back to Bell and Kochen–Specker. An algebraic approach is presented, allowing for a discussion of partial classical extension, amounting to reduction of the “number of contexts,” classical representability arising as a special case. As a result, known techniques are generalized and some of the associated computational difficulties overcome. The implications on the discussion of Boole–Bell inequalities are indicated.
Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.
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 .
The logical structures studied in this paper are generalizations of the propositional calculus. The classical propositional calculus is essentially Boolean algebra or, alternatively, the theory of functions on an arbitrary set S with values in a two-element set. The generalization consists in allowing partial functions on the set S , i.e., functions defined on certain subsets of S , and defining an equivalence relation among these functions such that any two constant functions with the same constant value belong to the same equivalence class. The generalization is equally natural for functions with values in the field of real numbers and we shall consider this case first. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Partial Boolean algebras (PBAs) were introduced by Kochen and Specker as an algebraic model reflecting the mutual relationships among quantum-physical yes–no tests. The fact that not all pairs of tests are compatible was taken into special account. In this paper, we review PBAs from two sides. First, we generalise the concept, taking into account also those yes–no tests which are based on unsharp measurements. Namely, we introduce partial MV-algebras, and we define a corresponding logic. Second, we turn to the representation theory of PBAs. In analogy to the case of orthomodular lattices, we give conditions for a PBA to be isomorphic to the PBA of closed subspaces of a complex Hilbert space. Hereby, we do not restrict ourselves to purely algebraic statements; we rather give preference to conditions involving automorphisms of a PBA. We conclude by outlining a critical view on the logico-algebraic approach to the foundational problem of quantum physics.
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.