@inproceedings{50273,
  abstract     = {{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}}$.}},
  author       = {{Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}},
  booktitle    = {{Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}},
  number       = {{7}},
  pages        = {{7--17}},
  title        = {{{Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds}}},
  doi          = {{10.4230/LIPIcs.MFCS.2024.7}},
  volume       = {{306}},
  year         = {{2024}},
}