Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification

In the classical world, an extremely fruitful technique for constructing interactive protocols is "compiling" a multiprover game, using cryptography to simulate the separation between the provers. In the quantum world, the study of compiled nonlocal games was introduced by Kalai et al. (STOC'23), who defined a compilation procedure that applies to any nonlocal game and preserves the classical value; however, they did not show any bounds on the quantum value of their protocols. In this work, we make progress towards a full understanding of the quantum value of compiled nonlocal games. For the special case of the CHSH game, we show that the Tsirelson bound holds for the compiled game in two ways: by extending the "macroscopic locality" argument of Rohrlich, and by showing that strategies for the compiled game yield feasible solutions to the Tsirelson SDP. We conjecture that the latter argument can be extended to all XOR games. Using our SDP argument, we are able to recover a strong version of the "rigidity" property that makes CHSH so useful in applications; specifically, we show that compiled CHSH is a "computational self-test" in the sense of Metger and Vidick. As an application, we give a classical verification protocol for BQP based on a compiled nonlocal game and prove soundness. Our protocol replicates the functionality of Mahadev '18 but with two advantages: (1) the soundness analysis is much simpler, and directly follows the analysis of the nonlocal case, and (2) the soundness does not "explicitly" use the assumption of a TCF or an adaptive hardcore bit, and only requires QFHE as a black box (though currently the only known constructions of QFHE use TCFs).