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

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.

Available format(s)
Publication info
Non-local games CHSH Quantum advantage Homomorphic Encryption
Contact author(s)
yael @ microsoft com
alexlombardi @ alum mit edu
vinodv @ mit edu
lisayang @ mit edu
2022-09-30: last of 2 revisions
2022-03-28: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.