Quantum generalizations of the polynomial hierarchy with applications to QMA(2)

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}$.

v2 adds some observations on connections between Quantum Refereed Games and $\mathrm{Q}{\Sigma }_2$

References in corpus (9)

• N-representability is QMA-complete
• A Simple Proof that Toffoli and Hadamard are Quantum Universal
• Quantum NP - A Survey
• Revisiting the simulation of quantum Turing machines by quantum circuits
• Importance of the spectral gap in estimating ground-state energies
• Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
• The complexity of simulating local measurements on quantum systems
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• Quantum State Isomorphism

Cited by in corpus (7)

• Importance of the spectral gap in estimating ground-state energies
• The complexity of simulating local measurements on quantum systems
• Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
• A fidelity measure for quantum states based on the matrix geometric mean
• The 7 faces of quantum NP
• Towards a quantum-inspired proof for IP = PSPACE
• The Acrobatics of BQP