Abstract:
Interactive proofs are a classic idea in complexity theory, with the study of mulitprover interactive proof systems leading to advances such as the PCP theorem. Remarkably, in quantum information, such proof systems have become an important tool for studying quantum entanglement, extending the pioneering work of Bell in the 1960s. In this talk I will talk about recent progress in characterizing the power of the complexity class MIP* of multiprover interactive proof systems where the provers share entanglement. In addition to revealing an area of quantum complexity theory that is strikingly different from its classical counterpart, this work has led to new protocols for testing entanglement and delegating quantum computations, as well as to consequences for the Connes embedding problem in operator algebras.
Based on joint works with Thomas Vidick, John Wright, Zhengfeng Ji, and Henry Yuen.
Biography:
Anand Natarajan is a postdoc in Computing and Mathematical Sciences at Caltech. He completed his PhD in Physics at MIT supervised by Aram Harrow. His research is in the theory of quantum computing, with a focus on quantum complexity theory.
