Quantum logic generalizes, and in dimension one coincides with, Boolean
logic. We show that the satisfiability problem of quantum logic formulas is
NP-complete in dimension two as well. For higher higher-dimensional spaces R^d
and C^d with d>2 fixed, we establish quantum satisfiability to be polynomial
time equivalent to the real feasibility of a multivariate quartic polynomial
equation: a problem well-known complete for the counterpart of NP in the
Blum-Shub-Smale model of computation lying (probably strictly) between
classical NP and PSPACE.