{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/159113"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/159113","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"A Computational Tsirelson's Theorem for All Compiled Nonlocal Games","abstract":"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","abstract_html":"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","abstract_has_math":false,"creators":["Falor, Chirag"],"institution":"Massachusetts Institute of Technology","degree_name":"Master","degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science","school":null,"contributors":[],"advisors":["Natarajan, Anand"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-02","date_published":"2025-02","updated_at":"2026-07-22T22:21:50Z","subjects":[],"languages":[],"rights":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"],"rights_urls":["https://rightsstatements.org/page/InC-EDU/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1721.1/159113","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Natarajan, Anand"]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"]},{"key":"dc:creator","label":"Author","values":["Falor, Chirag"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-04-14T14:06:24Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-04-14T14:06:24Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-02"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master","Master of Engineering in Electrical Engineering and Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://rightsstatements.org/page/InC-EDU/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1721.1/159113"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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"]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M.Eng."]},{"key":"dc:title","label":"Title","values":["A Computational Tsirelson's Theorem for All Compiled Nonlocal Games"]}]}],"canonical_facts":{"dc:contributor.advisor":["Natarajan, Anand"],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science"],"dc:creator":["Falor, Chirag"],"dc:date.accessioned":["2025-04-14T14:06:24Z"],"dc:date.available":["2025-04-14T14:06:24Z"],"dc:date.issued":["2025-02"],"dc:description.abstract":["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"],"dc:description.degree":["M.Eng."],"dc:identifier.uri":["https://hdl.handle.net/1721.1/159113"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["In Copyright - Educational Use Permitted","Copyright retained by author(s)"],"dc:rights.uri":["https://rightsstatements.org/page/InC-EDU/1.0/"],"dc:title":["A Computational Tsirelson's Theorem for All Compiled Nonlocal Games"],"dc:type":["Thesis"],"thesis:degree_name":["Master","Master of Engineering in Electrical Engineering and Computer Science"]},"updated_at":"2026-07-22T22:21:50Z"}