  A binary constraint system game is a two-player one-round non-local game
defined by a system of Boolean constraints. The game has a perfect quantum
strategy if and only if the constraint system has a quantum satisfying
assignment [R. Cleve and R. Mittal, arXiv:1209.2729]. We show that several
concepts including the quantum chromatic number and the Kochen-Specker sets
that arose from different contexts fit naturally in the binary constraint
system framework. The structure and complexity of the quantum satisfiability
problems for these constraint systems are investigated. Combined with a new
construct called the commutativity gadget for each problem, several classic
NP-hardness reductions are lifted to their corresponding quantum versions. We
also provide a simple parity constraint game that requires $\Omega(\sqrt{n})$
EPR pairs in perfect strategies where $n$ is the number of variables in the
constraint system.
