  Quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann
as a framework for capturing the logical peculiarities of quantum observables.
It generalizes, and on 1-dimensional Hilbert space coincides with, Boolean
propositional logic.
  We introduce the weak and strong satisfiability problem for quantum logic
terms. It turns out that in dimension two both are also NP-complete.
  For higher-dimensional spaces R^d and C^d with d>2 fixed, on the other hand,
we show both problems 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 extends the still relatively scarce family of
NP_R-complete problems with one perhaps closest in spirit to the classical
Cook-Levin Theorem.
  Our investigations on the dimensions a term is weakly/strongly satisfiable in
lead to satisfiability problems in indefinite finite and finally in infinite
dimension. Here, strong satisfiability turns out as polynomial-time equivalent
to the feasibility of noncommutative integer polynomial equations
