Compiled nonlocal games: sum-of-squares optimization meets cryptography?
Presenter
April 25, 2023
Abstract
Nonlocal games are a fundamental tool for testing quantum systems, but their power depends on spatial separation: a verifier must be able to separately interact with two quantum systems that cannot communicate with each other. In 2022, Kalai, Lombardi, Vaikuntanathan, and Yang proposed a method to "compile" any nonlocal game into an interaction with a *single* quantum device, using cryptography to simulate spatial separation. However, they could not characterize the behavior of quantum devices in their protocols (only classical devices). In this work, we make progress on this question by showing that the compiled version of the CHSH game forces the device to use two anti-commuting observables, just as the nonlocal version does, and as a consequence obtain an efficient argument system for polynomial-time quantum computations. Our proof is based on a modification of the noncommutative sum-of-squares method, which is one of the few general techniques known to analyze nonlocal games. Joint work with Tina Zhang, MIT.