Complexity Theory for Quantum Promise Problems

Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang +1

We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, ${\text{p/mQSZK}}_{\text{hv}}$, p/mQIP, p/mBQP/qpoly, p/mBQP/poly,…