Theory Lunch Seminar

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • JOHN WRIGHT
  • Postdoctoral Researcher
  • Cener for Theoretical Physics
  • Massachusetts Institute of Technology
Seminars

NEEXP in MIP*

A long-standing puzzle in quantum complexity theory is to understand the power of the class MIP* of multiprover interactive proofs with shared entanglement. This question is closely related to the study of entanglement through non-local games, which dates back to the pioneering work of Bell. In this work we show that MIP* contains NEEXP (non-deterministic doubly-exponential time), exponentially improving the prior lower bound of NEXP due to Ito and Vidick. Our result shows that shared entanglement exponentially increases the power of these proof systems, as the class MIP of multiprover interactive proofs without shared entanglement is known to be equal to NEXP.

This is joint work with Anand Natarajan.

CMU Youtube Theory channel

For More Information, Please Contact: 
Keywords: