A Complexity Theory for the Quantum Age?

Explore quantum complexity theory in this 37-minute conference talk by Henry Yuen from Columbia University. Delve into the challenges of adapting classical complexity theory to the quantum realm, examining topics such as search vs. decision problems, entanglement, and quantum transformations. Investigate the intriguing connections between quantum complexity and the Black Hole Information Paradox through a thought experiment. Gain insights into the computational difficulties faced in quantum systems and understand the potential implications for a new complexity theory in the quantum age.

Introduction
Goals
Search vs Decision Problems
Mickey Mouse
entanglement
formal evidence
Quantum transformations
Why this problem
The Black Hole Information Paradox
A Thought Experiment
Computational Difficulties
Summary