Computer Science Department Master Calendar

Back to Listing

Anand Natarajan, "Interactive Proofs and Quantum Entanglement"

Event Type
Lecture
Topic
special seminar
Sponsor
Illinois Computer Science
Location
2405 Siebel Center
Date
Jan 30, 2020   10:00 - 11:00 am  
Cost
Free
Contact
Samantha Smith
E-Mail
sdsmith3@illinois.edu
Views
508
Originating Calendar
Computer Science Speakers Calendar

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.

link for robots only