Quantum Advantage from Any Non-local Game

Yael Kalai; Alex Lombardi; Vinod Vaikuntanathan; Lisa Yang

doi:10.1145/3564246.3585164

Quantum Advantage from Any Non-local Game

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	American English
Title of host publication	STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
Editors	Barna Saha, Rocco A. Servedio
Publisher	Association for Computing Machinery
Pages	1617-1628
Number of pages	12
ISBN (Electronic)	9781450399135
DOIs	https://doi.org/10.1145/3564246.3585164
State	Published - Jun 2 2023
Externally published	Yes
Event	55th Annual ACM Symposium on Theory of Computing, STOC 2023 - Orlando, United States Duration: Jun 20 2023 → Jun 23 2023

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing

Conference

Conference	55th Annual ACM Symposium on Theory of Computing, STOC 2023
Country/Territory	United States
City	Orlando
Period	6/20/23 → 6/23/23

ASJC Scopus subject areas

Software

Keywords

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

Access to Document

10.1145/3564246.3585164

Cite this

Kalai, Y., Lombardi, A., Vaikuntanathan, V., & Yang, L. (2023). Quantum Advantage from Any Non-local Game. In B. Saha, & R. A. Servedio (Eds.), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 1617-1628). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3564246.3585164

@inproceedings{7aaf936a7f224123886b9ff78c00fbcb,

title = "Quantum Advantage from Any Non-local Game",

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.",

keywords = "Quantum computational advantage, cryptographic protocols, non-local games, quantum homomorphic encryption",

author = "Yael Kalai and Alex Lombardi and Vinod Vaikuntanathan and Lisa Yang",

note = "Publisher Copyright: {\textcopyright} 2023 Owner/Author.; 55th Annual ACM Symposium on Theory of Computing, STOC 2023 ; Conference date: 20-06-2023 Through 23-06-2023",

year = "2023",

month = jun,

day = "2",

doi = "10.1145/3564246.3585164",

language = "American English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "1617--1628",

editor = "Barna Saha and Servedio, {Rocco A.}",

booktitle = "STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing",

}

Kalai, Y, Lombardi, A, Vaikuntanathan, V & Yang, L 2023, Quantum Advantage from Any Non-local Game. in B Saha & RA Servedio (eds), STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 1617-1628, 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, United States, 6/20/23. https://doi.org/10.1145/3564246.3585164

Quantum Advantage from Any Non-local Game. / Kalai, Yael; Lombardi, Alex; Vaikuntanathan, Vinod et al.
STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing. ed. / Barna Saha; Rocco A. Servedio. Association for Computing Machinery, 2023. p. 1617-1628 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Quantum Advantage from Any Non-local Game

AU - Kalai, Yael

AU - Lombardi, Alex

AU - Vaikuntanathan, Vinod

AU - Yang, Lisa

PY - 2023/6/2

Y1 - 2023/6/2

N2 - 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.

AB - 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.

KW - Quantum computational advantage

KW - cryptographic protocols

KW - non-local games

KW - quantum homomorphic encryption

UR - http://www.scopus.com/inward/record.url?scp=85163064185&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163064185&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585164

DO - 10.1145/3564246.3585164

M3 - Conference contribution

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1617

EP - 1628

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -

Quantum Advantage from Any Non-local Game

Abstract

Publication series

Conference

ASJC Scopus subject areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this