Paper 2024/1276
A bound on the quantum value of all compiled nonlocal games
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.
Note: Preprint
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- non-local gamesKLVY compilerquantum soundnesshomomorphic encryption
- Contact author(s)
-
alexander kulpe @ rub de
giulio malavolta @ unibocconi it
cpaulpad @ uottawa ca
s schmidt @ rub de
michael walter @ rub de - History
- 2024-08-16: approved
- 2024-08-13: received
- See all versions
- Short URL
- https://ia.cr/2024/1276
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1276,
author = {Alexander Kulpe and Giulio Malavolta and Connor Paddock and Simon Schmidt and Michael Walter},
title = {A bound on the quantum value of all compiled nonlocal games},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1276},
year = {2024},
url = {https://eprint.iacr.org/2024/1276}
}
