The Polynomial-Time Hierarchy (
PH) is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum advantage'' analyses for near-term quantum computers. Quantumly, however, despite the fact that at least \emph{four} definitions of quantum
PH exist, it has been challenging to prove analogues for these of even basic facts from
PH. This work studies three quantum-verifier based generalizations of
PH, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings (
QCPH) and quantum mixed states (
QPH) as proofs, and one of which is new to this work, utilizing quantum pure states (
pureQPH) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for
QCPH. Then, for our new class
pureQPH, we show one-sided error reduction for
pureQPH, as well as the first bounds relating these quantum variants of
PH, namely
QCPH⊆pureQPH⊆EXPPP.
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,
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Σ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
Ppppp ). Second, because
QMA(2)⊆QΣ3 ,
QMA(2) is strictly contained in NEXP unless
QMA(2)=QΣ3 (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').
In 1889, A. A. Markov proved a powerful result about low-degree real polynomials: roughly speaking, that such polynomials cannot have a sharp jump followed by a long, relatively flat part. A century later, this result - as well as other results from the field of approximation theory - came to play a surprising role in classical and quantum complexity theory. In this article, the author tries to tell this story in an elementary way, beginning with classic results in approximation theory and ending with some recent applications.
The polynomial hierarchy plays a central role in classical complexity theory. Here, we define a quantum generalization of the polynomial hierarchy, and initiate its study. We show that not only are there natural complete problems for the second level of this quantum hierarchy, but that these problems are in fact hard to approximate. Using the same techniques, we also obtain hardness of approximation for the class QCMA. Our approach is based on the use of dispersers, and is inspired by the classical results of Umans regarding hardness of approximation for the second level of the classical polynomial hierarchy [Umans, FOCS 1999]. The problems for which we prove hardness of approximation for include, among others, a quantum version of the Succinct Set Cover problem, and a variant of the local Hamiltonian problem with hybrid classical-quantum ground states.