Extra Theory Seminar - NEEXP in MIP*

Abstract: 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.

Bio: John Wright received a B.Sc. from the University of Texas at Austin in 2010 and a Ph.D. from the CMU Computer Science Department in 2016. His Ph.D. advisor was Ryan O'Donnell. From 2016 through 2019, he was a postdoc at the MIT Center for Theoretical Physics in Eddie Farhi, Aram Harrow, and Peter Shor's group. He is currently a postdoc at the Institute for Quantum Information and Matter in Caltech under Fernando Brandao, Thomas Vidick, and John Preskill. In 2020, he will join UT Austin as an assistant professor of computer science. His research areas include quantum information theory and quantum complexity theory