Complexity Theory for Quantum Promise Problems

Understand

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, and p/mPSPACE.

• This includes identifying complete problems, as well as proving containment and separation results among these classes.
• Here, p/mC denotes the corresponding quantum promise complexity class with pure (p) or mixed (m) quantum input states for any classical complexity class C.
• Surprisingly, our findings uncover relationships that diverge from their classical analogues -- specifically, we show unconditionally that p/mQIP$\neq$p/mPSPACE and p/mBQP/qpoly$\neq$p/mBQP/poly.