ECCC-Report TR24-006https://eccc.weizmann.ac.il/report/2024/006Comments and Revisions published for TR24-006en-usSun, 14 Jan 2024 11:11:32 +0200
Paper TR24-006
| The Entangled Quantum Polynomial Hierarchy Collapses |
Sabee Grewal,
Justin Yirka
https://eccc.weizmann.ac.il/report/2024/006We introduce the entangled quantum polynomial hierarchy $QEPH$ as the class of problems that are efficiently verifiable given alternating quantum proofs that may be entangled with each other. We prove $QEPH$ collapses to its second level. In fact, we show that a polynomial number of alternations collapses to just two. As a consequence, $QEPH = QRG(1)$, the class of problems having one-turn quantum refereed games, which is known to be contained in $PSPACE$. This is in contrast to the unentangled quantum polynomial hierarchy $QPH$, which contains $QMA(2)$.
We also introduce a generalization of the quantum-classical polynomial hierarchy $QCPH$ where the provers send probability distributions over strings (instead of strings) and denote it by $DistributionQCPH$. Conceptually, this class is intermediate between $QCPH$ and $QPH$. We prove ${DistributionQCPH} = {QCPH}$, suggesting that only quantum superposition (not classical probability) increases the computational power of these hierarchies. To prove this equality, we generalize a game-theoretic result of Lipton and Young (1994) which says that the provers can send distributions that are uniform over a polynomial-size support. We also prove the analogous result for the polynomial hierarchy, i.e., ${DistributionPH} = {PH}$. These results also rule out certain approaches for showing ${QPH}$ collapses.
Finally, we show that ${PH}$ and ${QCPH}$ are contained in ${QPH}$, resolving an open question of Gharibian et al. (2022).Sun, 14 Jan 2024 11:11:32 +0200https://eccc.weizmann.ac.il/report/2024/006