| Title: |
Unitary Complexity and the Uhlmann Transformation Problem |
| Authors: |
Bostanci, John; Efron, Yuval; Metger, Tony; Poremba, Alexander; Qian, Luowen; Yuen, Henry |
| Contributors: |
John Bostanci and Yuval Efron and Tony Metger and Alexander Poremba and Luowen Qian and Henry Yuen |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
Uhlmann’s theorem; unitary complexity theory |
| Description: |
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. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.24 |
| DOI: |
10.4230/LIPIcs.ITCS.2026.24 |
| Availability: |
https://doi.org/10.4230/LIPIcs.ITCS.2026.24; https://nbn-resolving.org/urn:nbn:de:0030-drops-253111; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.24 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.4226F9C0 |
| Database: |
BASE |