Name
Abstract | ||
|---|---|---|
The polynomial-time hierarchy ($\mathrm{PH}$) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as $\mathrm{PH}$ does not collapse). Here, we study whether two quantum generalizations of $\mathrm{PH}$ can similarly prove separations in the quantum setting. The first generalization, $\mathrm{QCPH}$, uses classical proofs, and the second, $\mathrm{QPH}$, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $\mathrm{Q} \Sigma_3$, into $\mathrm{NEXP}$ {using the Ellipsoid Method for efficiently solving semidefinite programs}. These results yield two implications for $\mathrm{QMA}(2)$, the variant of Quantum Merlin-Arthur ($\mathrm{QMA}$) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $\mathrm{QCPH} = \mathrm{QPH}$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then $\mathrm{QMA}(2)$ is in the Counting Hierarchy (specifically, in $\mathrm{P}^{\mathrm{PP}^{\mathrm{PP}}}$). Second, unless $\mathrm{QMA}(2)={\mathrm{Q} \Sigma_3}$ (i.e., alternating quantifiers do not help in the presence of "unentanglement"), $\mathrm{QMA}(2)$ is strictly contained in $\mathrm{NEXP}$. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.MFCS.2018.58 | mathematical foundations of computer science |
DocType | Volume | ISSN |
Conference | abs/1805.11139 | Proceedings of 43rd International Symposium on Mathematical
Foundations of Computer Science (MFCS 2018) |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| sevag gharibian | 1 | 44 | 7.72 |
| Miklos Santha | 2 | 728 | 92.42 |
| Jamie Sikora | 3 | 9 | 4.29 |
| Aarthi Sundaram | 4 | 4 | 3.18 |
| Justin Yirka | 5 | 0 | 1.01 |