---
res:
bibo_abstract:
- The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing
separations in computational complexity theory (modulo standard conjectures such
as PH does not collapse). Here, we study whether two quantum generalizations of
PH can similarly prove separations in the quantum setting. The first generalization,
QCPH, uses classical proofs, and the second, 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, Q Sigma_3, into NEXP using the Ellipsoid
Method for efficiently solving semidefinite programs. These results yield two
implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled
proofs, a complexity class whose characterization has proven difficult. First,
if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to
make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting
Hierarchy (specifically, in P^{PP^{PP}}). Second, unless QMA(2)= Q Sigma_3 (i.e.,
alternating quantifiers do not help in the presence of "unentanglement"), QMA(2)
is strictly contained in NEXP.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
- foaf_Person:
foaf_givenName: Miklos
foaf_name: Santha, Miklos
foaf_surname: Santha
- foaf_Person:
foaf_givenName: Jamie
foaf_name: Sikora, Jamie
foaf_surname: Sikora
- foaf_Person:
foaf_givenName: Aarthi
foaf_name: Sundaram, Aarthi
foaf_surname: Sundaram
- foaf_Person:
foaf_givenName: Justin
foaf_name: Yirka, Justin
foaf_surname: Yirka
bibo_doi: 10.4230/LIPIcs.MFCS.2018.58
bibo_volume: 117
dct_date: 2018^xs_gYear
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik@
dct_subject:
- Complexity Theory
- Quantum Computing
- Polynomial Hierarchy
- Semidefinite Programming
- QMA(2)
- Quantum Complexity
dct_title: Quantum Generalizations of the Polynomial Hierarchy with Applications
to QMA(2)@
...