Paper 2022/400
Quantum Advantage from Any Non-Local Game
Abstract
We show a general method of compiling any $k$-prover non-local game into a single-prover interactive game maintaining the same (quantum) completeness and (classical) soundness guarantees (up to negligible additive factors in a security parameter). Our compiler uses any quantum homomorphic encryption scheme (Mahadev, FOCS 2018; Brakerski, CRYPTO 2018) satisfying a natural form of correctness with respect to auxiliary (quantum) input. The homomorphic encryption scheme is used as a cryptographic mechanism to simulate the effect of spatial separation, and is required to evaluate $k-1$ prover strategies (out of $k$) on encrypted queries. In conjunction with the rich literature on (entangled) multi-prover non-local games starting from the celebrated CHSH game (Clauser, Horne, Shimonyi and Holt, Physical Review Letters 1969), our compiler gives a broad framework for constructing mechanisms to classically verify quantum advantage.
Note: Included simple special-case analysis for the CHSH game in the technical overview.
Metadata
- Available format(s)
-
PDF
- Publication info
- Preprint.
- Keywords
- Non-local games CHSH Quantum advantage Homomorphic Encryption
- Contact author(s)
-
yael @ microsoft com
alexlombardi @ alum mit edu
vinodv @ mit edu
lisayang @ mit edu - History
- 2022-09-30: last of 2 revisions
- 2022-03-28: received
- See all versions
- Short URL
- https://ia.cr/2022/400
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/400,
author = {Yael Tauman Kalai and Alex Lombardi and Vinod Vaikuntanathan and Lisa Yang},
title = {Quantum Advantage from Any Non-Local Game},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/400},
year = {2022},
url = {https://eprint.iacr.org/2022/400}
}
