CFCS Youth Talks

Quantum Advantage from Any Non-Local Game

  • Dr. Alex Lombardi, Simons-Berkeley
  • Time: 2023-08-04 15:00
  • Host: Dr. Tianren Liu
  • Venue: Room 204, Courtyard No.5, Jingyuan


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.