Marcin Kozik

Classical Simulation of Quantum CSP Strategies

2025

We prove 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 …