Classical simulation of quantum CSP strategies

Demian Banakh ( Jagiellonian University )

In this talk, I will first introduce the paradigm of 2-prover 1-round games. Then we shall consider different classical and quantum resources, and the advantage that they provide the provers with. Finally, I sketch a proof that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on the size of the shared quantum system, and structural parameters of the CSP template. A byproduct of this result is that the gap between the classical chromatic number of graphs and its quantum variant is bounded whenever the size of the shared quantum system is bounded. This is a joint work with Lorenzo Ciardo, Marcin Kozik, and Jan Tułowiecki.