Quantum constraint satisfaction problems (QuCSPs)

Duration: 1 January 2027 – 31 December 2030

Annotation. Constraint satisfaction problems (CSPs) capture fundamental computational problems. CSP consists of variables and constraints. The goal is to find an assignment of values to all the variables in such a way that all the constraints are satisfied. CSPs can also be presented as nonlocal games. Nonlocal games, which grew out of the study of Bell inequalities in physics, provide a framework for studying quantum entanglement. In a nonlocal game, Alice and Bob, who may not communicate but may come up with a strategy in advance, try to correctly respond to questions given to each by a referee. They can use a classical strategy, or a quantum strategy, in which the players determine their answers by performing independent measurements on a shared entangled state. Alice and Bob want to maximize the winning probability. The quantum advantage is when the maximum winning probability of a quantum strategy is larger than that of any classical strategy. Our goals are twofold: (1) to study the power of quantum entanglement in the setting of CSPs; (2) to study how the computational complexity of deciding CSPs relates to that of deciding the winning probability.