Unitary Complexity and the Uhlmann Transformation Problem

State transformation problems such decoding noisy quantum channels or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. In this talk, I will discuss how the ``Uhlmann Transformation Problem’’, an algorithmic version of Uhlmann’s theorem, serves as a useful framework to study the complexity of state transformation tasks. I will mainly focus on cryptographic applications of the Uhlmann Transformation Problem, such as the task of breaking quantum commitment schemes and one-way state generators, and even falsifiable quantum cryptographic assumptions more generally. No quantum background required. This talk is based on recent joint work with John Bostanci, Yuval Efron, Tony Metger, Luowen Qian and Henry Yuen: https://arxiv.org/abs/2306.13073