Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-006 | 14th January 2024 08:45

The Entangled Quantum Polynomial Hierarchy Collapses


Authors: Sabee Grewal, Justin Yirka
Publication: 14th January 2024 11:11
Downloads: 67


We 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).

ISSN 1433-8092 | Imprint