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.
Go to Source of this post
Author Of this post: <a href="http://arxiv.org/find/quant-ph/1/au:+Kalai_Y/0/1/0/all/0/1">Yael Kalai</a>, <a href="http://arxiv.org/find/quant-ph/1/au:+Lombardi_A/0/1/0/all/0/1">Alex Lombardi</a>, <a href="http://arxiv.org/find/quant-ph/1/au:+Vaikuntanathan_V/0/1/0/all/0/1">Vinod Vaikuntanathan</a>, <a href="http://arxiv.org/find/quant-ph/1/au:+Yang_L/0/1/0/all/0/1">Lisa Yang</a>