Interactive proofs and quantum entanglement
Monday,
February 17, 2020
11:40 AM - 12:40 PM
SEAS Quantum Initiative Seminar
Anand Natarajan (Caltech)
ABSTRACT:
Interactive proof systems are a classic idea in theoretical computer science, and have led to fundamental advances in complexity theory (hardness of approximation and the PCP theorem) and cryptography. Remarkably, in quantum information, interactive proof systems with multiple provers have become an important tool for studying quantum entanglement, extending the pioneering work of Bell in the 1960s.
In this talk I will discuss recent progress in characterizing the power of the complexity class MIP* of such 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 schemes for delegating quantum computations to untrusted servers, as well as to consequences for the Connes embedding problem in operator algebras. At the heart of this work are new protocols that use classical PCP techniques together with the rules of quantum mechanics to let a classical client precisely control an untrusted quantum server.
BIO:
Anand Natarajan is a postdoc in Computing and Mathematical Sciences at Caltech. He completed his PhD in Physics at MIT supervised by Aram Harrow.
Natarajan's research is in the theory of quantum computing, with a focus on quantum complexity theory.
Anand Natarajan (Caltech)
ABSTRACT:
Interactive proof systems are a classic idea in theoretical computer science, and have led to fundamental advances in complexity theory (hardness of approximation and the PCP theorem) and cryptography. Remarkably, in quantum information, interactive proof systems with multiple provers have become an important tool for studying quantum entanglement, extending the pioneering work of Bell in the 1960s.
In this talk I will discuss recent progress in characterizing the power of the complexity class MIP* of such 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 schemes for delegating quantum computations to untrusted servers, as well as to consequences for the Connes embedding problem in operator algebras. At the heart of this work are new protocols that use classical PCP techniques together with the rules of quantum mechanics to let a classical client precisely control an untrusted quantum server.
BIO:
Anand Natarajan is a postdoc in Computing and Mathematical Sciences at Caltech. He completed his PhD in Physics at MIT supervised by Aram Harrow.
Natarajan's research is in the theory of quantum computing, with a focus on quantum complexity theory.
LOCATION:
← BACK TO EVENTS
- Morningside
- Lecture
- Computer Science
- Alumni
- Faculty
- Family-friendly
- Graduate Students
- Postdocs
- Prospective Students
- Public
- Staff
- Students
- Trainees
Date Navigation Widget
Getting to Columbia
Other Calendars
- Alumni Events
- Barnard College
- Columbia Business School
- Columbia College
- Committee on Global Thought
- Heyman Center
- Jewish Theological Seminary
- Miller Theatre
- School of Engineering & Applied Science
- School of Social Work
- Teachers College
Guests With Disabilities
- Columbia University makes every effort to accommodate individuals with disabilities. Please notify us if you need any assistance by contacting the event’s point person. Alternatively, the Office of Disability Services can be reached at 212.854.2388 and [email protected]. Thank you.