PIRSA:24050012 Conference Quantum Information

DOI10.48660/24050012

Conference/School: Foundations of Quantum Computational Advantage

Slofstra, W. (2024). Binary constraint systems and MIP*. Perimeter Institute. https://pirsa.org/24050012

Slofstra, William. Binary constraint systems and MIP*. Perimeter Institute, May. 02, 2024, https://pirsa.org/24050012 

@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).

Resources

Next talk

Related Talks