Quantum Advantage from Any Non-local Game

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We show a general method of compiling any k-prover non-local game into a single-prover (computationally sound) interactive game maintaining the same quantum completeness and classical soundness guarantees, up to a negligible additive factor 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, Shimony and Holt, Physical Review Letters 1969), our compiler gives a broad and rich framework for constructing protocols that classically verify quantum advantage.

Original languageEnglish (US)
Title of host publicationSTOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
EditorsBarna Saha, Rocco A. Servedio
PublisherAssociation for Computing Machinery
Pages1617-1628
Number of pages12
ISBN (Electronic)9781450399135
DOIs
StatePublished - Jun 2 2023
Externally publishedYes
Event55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States
Duration: Jun 20 2023Jun 23 2023

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/TerritoryUnited States
CityOrlando
Period6/20/236/23/23

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Quantum computational advantage
  • cryptographic protocols
  • non-local games
  • quantum homomorphic encryption

Fingerprint

Dive into the research topics of 'Quantum Advantage from Any Non-local Game'. Together they form a unique fingerprint.

Cite this