Cryptology ePrint Archive: Report 2022/400

Quantum Advantage from Any Non-Local Game

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

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.

Category / Keywords: Non-local games, CHSH, Quantum advantage, Homomorphic Encryption

Date: received 28 Mar 2022, last revised 29 Mar 2022

Contact author: yaelism at gmail com, alexjl at mit edu, vinodv at mit edu, lisayang at mit edu

Available format(s): PDF | BibTeX Citation

Note: fixed font

Version: 20220329:172859 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]