Academia Sinica Logo

This work develops a new complexity-theoretic framework for quantum-input decision problems—referred to as quantum promise problems—and demonstrates their fundamental differences from tranditional complexity theory. We establish complete problems, unconditional separations, and structural containments for a range of quantum promise complexity classes, and apply this framework to shed new light on quantum cryptography, property testing, and unitary synthesis.