Complexity Theory for Quantum Promise Problems

Abstract

Quantum computing introduces many intriguing problems rooted in physics, often involving direct computations on quantum states, such as quantum state tomography and entanglement testing. Understanding the complexity of these problems can lead to significant insights, influencing both computer science and physics profoundly. However, current complexity theory primarily addresses classical problems—those with classical inputs and outputs—leaving a notable gap when it comes to fully characterizing quantum-input problems. Recent developments in quantum cryptography further highlight this gap, especially regarding the study of minimal cryptographic assumptions necessary for quantum cryptography.

In this talk, I will start with a brief review of traditional complexity theory. Then, I’ll introduce a new framework for exploring quantum promise problems—decision problems defined explicitly with quantum inputs—and the natural complexity classes analogous to those in traditional complexity theory: p/mBQP, p/mQ(C)MA, p/mQSZK_hv, p/mQIP, and p/mPSPACE. I’ll discuss some basic structural results we obtained for this new complexity theory and illustrate its applications to quantum cryptography, showing the usefulness of our complexity-theoretic framework.

Joint work with Nai-Hui Chia, Tzu-Hsiang Huang, and Jhih-Wei Shih.

線上視訊請點選連結

附件下載