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 do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, $$\rm{QCPH}$$ , uses classical proofs, and the second, $$\rm{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, $$\rm{Q\Sigma_3}$$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $$\rm{QMA(2)}$$ , the variant of Quantum Merlin-Arthur ( $$\rm{QMA}$$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $$\rm{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 $${\rm P}^{{\rm pp}^{{\rm pp}}}$$ ). Second, because $$\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$$ , $$\rm{QMA(2)}$$ is strictly contained in NEXP unless $$\rm{QMA(2)}=\rm{Q\Sigma_3}$$ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').

The canonical hard problems for NP and its quantum analogue, Quantum Merlin-Arthur (QMA), are MAX-k-SAT and the k-local Hamiltonian problem (k-LH), the quantum generalization of MAX-k-SAT, respectively. In recent years, however, an arguably even more physically motivated problem than k-LH has been formalized - the problem of simulating local measurements on ground states of local Hamiltonians (APX-SIM). Perhaps surprisingly, [Ambainis, CCC 2014] showed that APX-SIM is likely harder than QMA. Indeed, [Ambainis, CCC 2014] showed that APX-SIM is P^{QMA[log]}-complete, for P^{QMA[log]} the class of languages decidable by a P machine making a logarithmic number of adaptive queries to a QMA oracle. In this work, we show that APX-SIM is P^{QMA[log]}-complete even when restricted to physically motivated Hamiltonians, obtaining as intermediate steps a variety of related complexity-theoretic results. Specifically, we first give a sequence of results which together yield P^{QMA[log]}-hardness for APX-SIM on well-motivated Hamiltonians such as the 2D Heisenberg model: - We show that for NP, StoqMA, and QMA oracles, a logarithmic number of adaptive queries is equivalent to polynomially many parallel queries. Formally, P^{NP[log]}=P^{||NP}, P^{StoqMA[log]}=P^{||StoqMA}, and P^{QMA[log]}=P^{||QMA}. (The result for NP was previously shown using a different proof technique.) These equalities simplify the proofs of our subsequent results. - Next, we show that the hardness of APX-SIM is preserved under Hamiltonian simulations (à la [Cubitt, Montanaro, Piddock, 2017]) by studying a seemingly weaker problem, ∀-APX-SIM. As a byproduct, we obtain a full complexity classification of APX-SIM, showing it is complete for P, P^{||NP},P^{||StoqMA}, or P^{||QMA} depending on the Hamiltonians employed. - Leveraging the above, we show that APX-SIM is P^{QMA[log]}-complete for any family of Hamiltonians which can efficiently simulate spatially sparse Hamiltonians. This implies APX-SIM is P^{QMA[log]}-complete even on physically motivated models such as the 2D Heisenberg model. Our second focus considers 1D systems: We show that APX-SIM remains P^{QMA[log]}-complete even for local Hamiltonians on a 1D line of 8-dimensional qudits. This uses a number of ideas from above, along with replacing the "query Hamiltonian" of [Ambainis, CCC 2014] with a new "sifter" construction.