- Home »
- MIP* = RE

COVID-19 information for PI Residents and Visitors

MIP* denotes the class of problems that admit interactive proofs with quantum entangled provers. It has been an outstanding question to characterize the complexity of this class. Most notably, there was no known computable upper bound on MIP*.

We show that MIP* is equal to the class RE, the set of recursively enumerable languages. In particular, this shows that MIP* contains uncomputable problems. Through a series of known connections, this also yields a negative answer to Connesâ€™ Embedding Problem from the theory of operator algebras. In this talk, I will explain the connection between Connes' Embedding Problem, quantum information theory, and complexity theory. I will then give an overview of our approach, which involves reducing the Halting Problem to the problem of approximating the entangled value of nonlocal games.

Joint work with Zhengfeng Ji, Anand Natarajan, Thomas Vidick, and John Wright.

COVID-19 information for PI Residents and Visitors

Collection/Series:

Event Type:

Seminar

Scientific Area(s):

Speaker(s):

Event Date:

Wednesday, May 13, 2020 - 14:00 to 15:30

Location:

Other

Share This PageShare this on TwitterShare on FacebookPublish this post to LinkedInSubmit this post on reddit.com

©2012 Perimeter Institute for Theoretical Physics