Seminars
Home
Centers & Programs
Quantum Universe
Seminars
- FIELD
- Phys: QUC
- DATE
-
Jun 10 (Mon), 2024
- TIME
- 10:00 ~ 11:00
- PLACE
- 8309
- SPEAKER
- Bostanci, John
- HOST
- Hhan, Minki
- INSTITUTE
- Colombia University
- TITLE
- [GS_C_QI] A fully quantum complexity theory
- ABSTRACT
- Many important tasks in quantum computer science involve performing transformations on quantum states. Unlike in classical theory, there is evidence that suggests that these kinds of tasks can not be reduced to decision problems. To address this gap, I will describe a new framework for unitary synthesis problems, including notions of reductions and complexity classes. To highlight the power of this framework, I will talk about a problem of transforming an entangled state to another via local operations, called the Uhlmann transformation problem.
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.
- FILE
-