A Computational Tsirelson's Theorem for All Compiled Nonlocal Games

Nonlocal games, defined as cooperative tasks between spatially separated players, have been a foundational tool in the study of quantum advantage and have been useful in classically verifying quantum computations. To address the challenge posed by the spatial separation assumption, Kalai et al. (STOC' 23) introduced a compilation procedure that compiles any nonlocal game into an interactive game between a classical verifier and a computationally bounded quantum prover. This compilation preserves classical soundness and quantum completeness, though quantum soundness has been established only in the asymptotic limit of the security parameter or for specific classes of games. In this work, we advance towards a concrete framework to bound the quantum value of compiled nonlocal games. Building on the notion of nice sum-of-squares certificates, introduced by Natarajan and Zhang (FOCS' 23) to bound the value of the compiled CHSH game, we extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates. We show that this hierarchy converges to the optimal quantum value of the game. Additionally, we present a transformation to make any degree-1 sum-of-squares certificate nice. This approach provides a systematic method to reproduce known bounds for special classes of games and showcases the general applicability of the framework to low-degree certificates. Source code: https://github.com/chiragfalor/ Nice-SoS-SDP

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2025

Author dc:creator

• Falor, Chirag

Advisor dc:contributor.advisor

• Natarajan, Anand

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/159113

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/159113