Towards a Complexity Theory for the Quantum Age

Speaker: Henry Yuen , Columbia University

Date: Tuesday, February 27, 2024

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G449

Event Type: Seminar

Room Description: Refreshments at 4:00pm

Host: Anand Natarajan, MIT

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: TOC Seminar: Towards a Complexity Theory for the Quantum Age, by Henry Yuen, Tuesday, February 27, 2024 at 4:15pm (Refreshments at 4:00pm) in 32-G449

Abstract: How hard is it to compress a quantum state? To fast-forward the evolution of a local Hamiltonian? To unscramble the Hawking radiation of a black hole? Traditional complexity theory -- which is centered around decision problems and tasks with classical inputs and outputs -- appears inadequate for reasoning about the complexity of such tasks involving quantum inputs and outputs.

I'll discuss why we need a "fully quantum" complexity theory, and will describe some facets of such a theory. As a key illustration I'll explain how a "fully quantum" task called the Uhlmann Transformation Problem characterizes the complexity of seemingly unrelated problems, such as decoding noisy quantum channels, performing the Harlow-Hayden black hole radiation decoding task, and breaking the security of quantum bit commitment schemes. I will describe some of the many open problems and directions to explore in the world of fully quantum complexity theory.

Bio: Henry Yuen is an Associate Professor of Computer Science at Columbia University. His research focuses on the interplay between quantum computing, complexity theory, cryptography, and information theory. Yuen received a BA in mathematics from the University of Southern California in 2010, and received his PhD in computer science at MIT in 2016. He is a recipient of the NSF CAREER award and a Sloan Fellowship.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2024.

Created by Joanne Talbot Hanley at Thursday, February 08, 2024 at 9:50 AM.