Using nonlocal games to verify quantum advantage

In this talk, I will give a brief introduction to nonlocal games, followed by a discussion on the results from [1]. In this paper Kalai et al. show a connection between nonlocal games and classical verification of quantum advantage. Specifically, they construct a framework for compiling a k-prover nonlocal game into a single-prover interactive game. They use quantum homomorphic encryption to simulate the spatial separation that is required in nonlocal games, and then use the gap between the classical and quantum winning probabilities of the nonlocal game to verify quantum advantage.

References:  [1] Kalai, Yael, et al. "Quantum Advantage from Any Non-Local Game." arXiv preprint arXiv:2203.15877 (2022).