Computational Complexity of Quantum Satisfiability

Quantum logic generalizes, and in dimension one coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic formulas, and show both NP-complete in dimension two as well. For higher-dimensional spaces R
^d
and C
^d
with d≥3 fixed, on the other hand, we show the problem to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and adds (a perhaps more natural and combinatorially flavoured) one to the still sparse list of NP
_R
-complete problems, mostly pertaining to real algebraic geometry. Our proofs rely on (a careful examination of) works by John von Neumannas well as contributions by Hagge et. al (2005,2007,2009). We finally investigate the problem over Indefinite finite dimensions and relate it to NON-commutative semi algebraic geometry.