  The Mermin-Peres magic square is a celebrated example of a system of Boolean
linear equations that is not (classically) satisfiable but is satisfiable via
linear operators on a Hilbert space of dimension four. A natural question is
then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis,
and Severini answered this question for all Boolean Constraint Satisfaction
Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual
Horn-SAT, classical satisfiability and operator satisfiability is the same and
thus there is no gap; for all other Boolean CSPs, these notions differ as there
are gaps, i.e., there are unsatisfiable instances that are satisfiable via
operators on Hilbert spaces.
  We generalize their result to CSPs on arbitrary finite domains and give an
almost complete classification: First, we show that NP-hard CSPs admit a
separation between classical satisfiability and satisfiability via operators on
finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable
CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show
that tractable CSPs of unbounded width can simulate, in a
satisfiability-gap-preserving fashion, linear equations over an Abelian group
of prime order $p$; for such CSPs, we obtain a separation of classical
satisfiability and satisfiability via operators on infinite-dimensional Hilbert
spaces. Furthermore, if $p=2$, such CSPs also have gaps separating classical
satisfiability and satisfiability via operators on finite- and
infinite-dimensional Hilbert spaces.
