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.
In this talk I will discuss why we need a "fully quantum" complexity theory, and will describe some facets of such a theory. As a key illustration I will 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. Along the way I will describe many open problems and directions to explore in the world of fully quantum complexity theory.
Joint work with John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, and Luowen Qian.
(Please note that this talk will start 5 minutes late due to the previous seminar. )
*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*