Alexander Kulpe

Alexander Kulpe

PhD Student

Publications

Conference Papers

A bound on the quantum value of compiled nonlocal games

Accepted at QIP 2025 (Short Plenary Talk), 2024

A compiler introduced by Kalai et al. converts any nonlocal game into an interactive protocol with a single computationally-bounded prover. Although the compiler is known to be sound in the case of classical provers, as well as complete in the quantum case, quantum soundness has so far only been established for special classes of games. In this work, we establish a quantum soundness result for all compiled two-player nonlocal games. In particular, we prove that the quantum commuting operator value of the underlying nonlocal game is an upper bound on the quantum value of the compiled game. Our result employs techniques from operator algebras in a computational and cryptographic setting to establish information-theoretic objects in the asymptotic limit of the security parameter. It further relies on a sequential characterization of quantum commuting operator correlations which may be of independent interest.

Download Paper

Preprint

Compiled Nonlocal Games from any Trapdoor Claw-Free Function

Online at Cryptology ePrint Archive, 2024

A recent work of Kalai et al. (STOC 2023) shows how to compile any multi-player nonlocal game into a protocol with a single computationally-bounded prover. Subsequent works have built on this to develop new cryptographic protocols, where a completely classical client can verify the validity of quantum computation done by a quantum server. Their compiler relies on the existence of quantum fully-homomorphic encryption. In this work, we propose a new compiler for transforming nonlocal games into single-prover protocols. Our compiler is based on the framework of measurement-based quantum computation. It can be instantiated assuming the existence of \emph{any} trapdoor function that satisfies the claw-freeness property. Leveraging results by Natarajan and Zhang (FOCS 2023) on compiled nonlocal games, our work implies the existence of new protocols to classically verify quantum computation from potentially weaker computational assumptions than previously known.

Download Paper