Quantum Advantage from Any Non-Local Game

Yael Tauman Kalai; Alex Lombardi; Vinod Vaikuntanathan; Lisa Yang

Paper 2022/400

Quantum Advantage from Any Non-Local Game

Yael Tauman Kalai, Microsoft Research, Massachusetts Institute of Technology

Alex Lombardi, Massachusetts Institute of Technology

Vinod Vaikuntanathan, Massachusetts Institute of Technology

Lisa Yang, Massachusetts Institute of Technology

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 prover strategies (out of ) 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}
}