In this talk, we will discuss a quantum theory of constraint satisfaction problems in the framework of two-player one-round nonlocal games. Several concepts that arose from different contexts fit naturally in the theory. These include the quantum chromatic number of a graph, the Kochen-Specker sets and the quantum homomorphisms between graphs. We will design reductions between these quantum satisfaction problems by lifting several classic NP-hardness reductions, including for example the one of 3-SAT to 3-COLORING, to their corresponding quantum versions. The key of the constructions is a new construct called the commutativity gadget for each problem. We will also show that the magic square game is a naturally born anti-commutativity gadget, which can be used as the building block to design a game that requires a large amount of entanglement in its perfect strategies.

The talk will be accessible to the general CS audience and no knowledge of quantum computing or quantum mechanics is assumed.