The Polynomial-Time Hierarchy ($\mathsf{ PH}$) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however, despite the fact that at least \emph{ four} definitions of quantum $\mathsf{ PH}$ exist, it has been challenging to prove analogues for these of even basic facts from $\mathsf{ PH}$. This work studies three quantum-verifier based generalizations of $\mathsf{ PH}$, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings ($\mathsf{ QCPH}$) and quantum mixed states ($\mathsf{ QPH}$) as proofs, and one of which is new to this work, utilizing quantum pure states ($\mathsf{ pureQPH}$) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $\mathsf{ QCPH}$. Then, for our new class $\mathsf{ pureQPH}$, we show one-sided error reduction for $\mathsf{ pureQPH}$, as well as the first bounds relating these quantum variants of $\mathsf{ PH}$, namely $\mathsf{ QCPH}\subseteq \mathsf{ pureQPH} \subseteq \mathsf{ EXP}^{ \mathsf{ PP}}$.
Categories: cs.CC quant-ph