Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras

• URL: http://arxiv.org/abs/2602.24164v1
• Date: Fri, 27 Feb 2026 16:43:13 GMT
• Title: Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras
• Authors: Anuj Dawar, Nihil Shah,
• Abstract summary: We show that the satisfiability problem for the class of non-variable partial Boolean algebras is NP-complete.<n>We also show that the satisfiability problem for the class of all Hilbert spaces and all finite-dimensional Hilbert spaces is undecidable.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Finite-dimensional Lie algebras in bosonic quantum dynamics: The single-mode case [0.0]
  We study, classify, and explore the mathematical properties of finite-dimensional Lie algebras occurring in the quantum dynamics of single-mode and self-interacting bosonic systems.
  arXiv  Detail & Related papers  (2025-11-10T10:46:22Z)
• Real Quantum Mechanics in a Kahler Space [0.0]
  We show that standard quantum mechanics, formulated in a complex Hilbert space, admits an equivalent reformulation in a real Kahler space.<n>This framework preserves all essential features of quantum mechanics while offering a key advantage.
  arXiv  Detail & Related papers  (2025-04-23T16:01:25Z)
• Towards entropic uncertainty relations for non-regular Hilbert spaces [44.99833362998488]
  The Entropic Uncertainty Relations (EUR) result from inequalities that are intrinsic to the Hilbert space and its dual with no direct connection to the Canonical Commutation Relations.<n>The analysis of these EUR in the context of singular Hilbert spaces has not been addressed.
  arXiv  Detail & Related papers  (2025-03-24T23:41:50Z)
• Beyond trace class -- Tensor products of Hilbert spaces and operator ideals in quantum physics [0.0]
  Banach operator ideals are lurking in the foundations and philosophy of quantum physics and quantum information theory. We establish a canonical isomorphism between the Hilbert spaces $Hotimes (K otimes L)$ and $(H otimes K) otimes L$ (Theorem 3.8) and revisit the role of trace class operators. A few applications are specified, including the appropriateness of the class of Hilbert-Schmidt operators and an implied Banach operator ideal representation of the tensor product of two complex spaces $H otimes K$ (Proposition 3.4) and
  arXiv  Detail & Related papers  (2023-08-08T23:37:02Z)
• The Schmidt rank for the commuting operator framework [58.720142291102135]
  The Schmidt rank is a measure for the entanglement dimension of a pure bipartite state. We generalize the Schmidt rank to the commuting operator framework. We analyze bipartite states and compute the Schmidt rank in several examples.
  arXiv  Detail & Related papers  (2023-07-21T14:37:33Z)
• Connecting classical finite exchangeability to quantum theory [45.76759085727843]
  Exchangeability is a fundamental concept in probability theory and statistics.<n>It allows to model situations where the order of observations does not matter.<n>It is well known that both theorems do not hold for finitely exchangeable sequences.
  arXiv  Detail & Related papers  (2023-06-06T17:15:19Z)
• Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
  The percolation transition is defined through the appearance of the infinite cluster. We show that the exponentially increasing dimensionality of the Hilbert space makes its covering by finite-size hyperspheres inefficient. Our approach to the percolation transition in compact metric spaces may prove useful for its rigorous treatment in other contexts.
  arXiv  Detail & Related papers  (2022-10-15T13:53:21Z)
• Positive maps and entanglement in real Hilbert spaces [5.926203312586108]
  We study positive maps acting on a full matrix algebra over the reals. We provide a necessary and sufficient condition for a real map to admit a positive complexification. We show that the original PPT-squared conjecture implies a different conjecture for real maps.
  arXiv  Detail & Related papers  (2022-07-06T08:25:55Z)
• Axioms for the category of Hilbert spaces [0.0]
  We provide axioms that guarantee a category is equivalent to that of continuous linear functions between Hilbert spaces. This addresses a question about the mathematical foundations of quantum theory raised in reconstruction programmes such as those of von Neumann, Mackey, Jauch, Piron, Abramsky, and Coecke.
  arXiv  Detail & Related papers  (2021-09-15T16:41:23Z)
• Entanglement and Complexity of Purification in (1+1)-dimensional free Conformal Field Theories [55.53519491066413]
  We find pure states in an enlarged Hilbert space that encode the mixed state of a quantum field theory as a partial trace. We analyze these quantities for two intervals in the vacuum of free bosonic and Ising conformal field theories.
  arXiv  Detail & Related papers  (2020-09-24T18:00:13Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.