Binary constraint systems and MIP*

          @misc{ pirsa_PIRSA:24050012,
            doi = {10.48660/24050012},
            url = {https://pirsa.org/24050012},
            author = {Slofstra, William},
            keywords = {Quantum Information},
            language = {en},
            title = {Binary constraint systems and MIP*},
            publisher = {Perimeter Institute},
            year = {2024},
            month = {may},
            note = {PIRSA:24050012 see, \url{https://pirsa.org}}
          }
          

Abstract

Binary constraint system games are a generalization of the Mermin-Peres magic square game introduced by Cleve and Mittal. Thanks to the recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen, BCS games can be used to construct a proof system for any language in MIP*, the class of languages with a multiprover interactive proof system where the provers can share entanglement. This means that we can apply logical reductions for binary constraint systems to MIP* protocols, and also raises the question: how complicated do our constraint systems have to be to describe all of MIP*? In this talk, I'll give a general overview of this subject, including an application of logical reductions to showing that all languages in MIP* have a perfect zero knowledge proof system (joint work with Kieran Mastel), and one obstacle to expressing all of MIP* with linear constraints (joint work with Connor Paddock).