Please Enter Keywords
资源 63
[Lecture] Quantum Advantage from Any Non-Local Game
Aug. 04, 2023

Speaker: Dr. Alex Lombardi, Simons-Berkeley

Time: 15:00 p.m., August 4, 2023, GMT+8

Venue: Jingyuan Campus No.5 Courtyard Room 204


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. Our compiler uses a quantum homomorphic encryption scheme as a cryptographic mechanism to (provably) simulate the effect of spatial separation. In conjunction with the rich literature on (entangled) multi-prover non-local games, our compiler gives a broad framework for constructing mechanisms to classically verify quantum advantage.  Some follow-up work analyzing quantum soundness of some such protocols will also be discussed.

The talk is mainly based on joint work with Yael Kalai, Vinod Vaikuntanathan, and Lisa Yang (


Alex Lombardi is a Simons-Berkeley postdoctoral fellow hosted by Shafi Goldwasser. His current interests lie mainly in the theory and foundations of cryptography. He was a graduate student at MIT, advised by Vinod Vaikuntanathan. In the coming fall, Alex will join Princeton as an Assistant Professor of Computer Science.

Source: Center on Frontiers of Computing Studies