# Quantum Advantage from Any Non-Local Game

arXiv: https://arxiv.org/abs/2203.15877 · HTML: https://mlsanity.com/paper/2203.15877/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2022.

## Built on by (most cited first, 1 of 1)

- [A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games](https://mlsanity.com/paper/2311.10859/) (2023)

## Abstract (arXiv)

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.