Abstract: A compiler introduced by Kalai et al. (STOC'23) converts any nonlocal game into an interactive protocol with a single computationally-bounded prover. Although the compiler is known to be sound in the case of classical provers, as well as complete in the quantum case, quantum soundness has so far only been established for special classes of games. In this work, we establish a quantum soundness result for all compiled two-player nonlocal games. In particular, we prove that the quantum commuting operator value of the underlying nonlocal game is an upper bound on the quantum value of the compiled game. Our result employs techniques from operator algebras in a computational and cryptographic setting to establish information-theoretic objects in the asymptotic limit of the security parameter. It further relies on a sequential characterization of quantum commuting operator correlations which may be of independent interest.
Bio: Giulio is an Assistant Professor in the department of Computing Sciences at Bocconi University. His research focuses on mathematical aspects of cryptography, computer security, and quantum computing. Prior to joining Bocconi, Giulio was a tenure-track faculty at the Max Planck Institute for Security and Privacy, and before that a postdoc at UC Berkeley and at Carnegie Mellon University. In fall 2019 he spent a semester as a research fellow at the Simons Institute for the Theory of Computing. He completed his PhD in 2019 at Friedrich-Alexander University, where his thesis was recognized with the Staedtler-Stiftung dissertation prize. Giulio was awarded an ERC starting grant and the Heinz-Maier Leibnitz prize.