A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

David Cui; Giulio Malavolta; Arthur Mehta; Anand Natarajan; Connor Paddock; Simon Schmidt; Michael Walter; Tina Zhang

Paper 2024/348

A Computational Tsirelson's Theorem for the Value of Compiled XOR Games

David Cui, MIT

Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy

Arthur Mehta, University of Ottawa

Anand Natarajan, MIT

Connor Paddock, University of Ottawa

Simon Schmidt, Ruhr University Bochum

Michael Walter, Ruhr University Bochum

Tina Zhang, MIT

Abstract

Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work, we continue the study initiated by Kalai et al. (STOC '23) of compiled nonlocal games, played between a classical verifier and a single cryptographically limited quantum device. Our main result is that the compiler proposed by Kalai et al. is sound for any two-player XOR game. A celebrated theorem of Tsirelson shows that for XOR games, the quantum value is exactly given by a semidefinite program, and we obtain our result by showing that the SDP upper bound holds for the compiled game up to a negligible error arising from the compilation. This answers a question raised by Natarajan and Zhang (FOCS '23), who showed soundness for the specific case of the CHSH game. Using our techniques, we obtain several additional results, including (1) tight bounds on the compiled value of parallel-repeated XOR games, (2) operator self-testing statements for any compiled XOR game, and (3) a ``nice" sum-of-squares certificate for any XOR game, from which operator rigidity is manifest.

Metadata

Available format(s): PDF
Publication info: Preprint.
Keywords: nonlocal games homomorphic encryption
Contact author(s): dzcui @ mit edu
giulio malavolta @ hotmail it
amehta2 @ uottawa ca
anandn @ mit edu
cpaulpad @ uottawa ca
s schmidt @ rub de
michael walter @ rub de
tinaz @ mit edu
History: 2024-02-27: approved; 2024-02-27: received; See all versions
Short URL: https://ia.cr/2024/348
License: CC BY

BibTeX

@misc{cryptoeprint:2024/348,
      author = {David Cui and Giulio Malavolta and Arthur Mehta and Anand Natarajan and Connor Paddock and Simon Schmidt and Michael Walter and Tina Zhang},
      title = {A Computational Tsirelson's Theorem for the Value of Compiled XOR Games},
      howpublished = {Cryptology ePrint Archive, Paper 2024/348},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/348}},
      url = {https://eprint.iacr.org/2024/348}
}