Unitary Complexity and the Uhlmann Transformation Problem
The Quantum Algorithms seminar resumes in the spring of 2024. Learn about the world of quantum computing through lectures on a variety of topics, ranging from established findings to ongoing research, delivered by both students and researchers.
You can find information about the upcoming and past sessions on our website and through our mailing list. The sessions may not necessarily build upon each other, so it might be worthwhile to subscribe even if you can only attend one or two lectures.
The topic of the first session:
Topic
- Title: Unitary Complexity and the Uhlmann Transformation Problem
- Presenter: Tony Metger on video at QIP 2024
- Video: https://youtu.be/kb-zqj3UMG0
Coordinates
- Time: 2024 March 21, Thursday 16:15 (1 hour + questions)
- Place: BME Building I, IB134 (inside the SZIT department)
Abstract
State transformation problems such as compressing quantum information 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. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann’s theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.