The polynomial hierarchy has been widely studied in classical complexity theory. In this paper, we will generalize some commonly known results about the polynomial hierarchy to a version of the hierarchy extended to promise problems. This paper proposes new definitions of existential and universal operators for classes of promise problems. Applying these to BQP, we recover the hierarchy proposed by Gharibian et al. (MFCS 2018). Moreover, using our definition, we give an easy proof of the collapse of this hierarchy under a Karp-Lipton-like scenario, which was an open question for the original definition of Gharibian et al.
The polynomial hierarchy has been widely studied in classical complexity theory. In this paper, we will generalize some commonly known results about the polynomial hierarchy to a version of the hierarchy extended to promise problems. This paper proposes new definitions of existential and universal operators for classes of promise problems. Applying these to BQP, we recover the hierarchy proposed by Gharibian et al. (MFCS 2018). Moreover, using our definition, we give an easy proof of the collapse of this hierarchy under a Karp-Lipton-like scenario, which was an open question for the original definition of Gharibian et al.
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.
Despite the importance of the non-uniform Polynomial-Time Hierarchy (PH/poly) in classical complexity understanding the collapse conditions of the Polynomial-Time Hierarchy (PH), a quantum equivalent of PH/poly has yet to be studied in the literature. We introduce the non-uniform computational Quantum Polynomial-Time Hierarchy (QCPH/mpoly), the quantum equivalent of PH/poly, and show that it collapses if and only if QCPH, the quantum equivalent of PH introduced by Gharibian et al. (comput. complex. 2022), also collapses. We also show that QCPH collapses if coQCMA is contained in QCMA/mpoly. These results are analogous to those of Yap (TCS 1983) commonly used to invoke the collapse of PH in classical complexity. QCPH/mpoly is analogous to QCPH with non-uniform quantum verifier circuits.
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'').
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC0. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of the promise being unconstrained. We study two semantics for such access. Under robust queries, a machine must correctly answer regardless of the completion of the problem,, while loose access requires that the internal choices of a machine do not change based on off-promise queries.
Our first result separates the language and promise settings. Namely, we construct an oracle O such that PO=BQPO=AWPPO, but PromiseBQPO⊆PromiseP/polyO. In particular, BPPO=BQPO, but PromiseBQPO=PromiseBPPO, showing that results for languages need not transfer to promises. Next, we use loose queries to strengthen the upper bound on the Quantum-Classical Polynomial Hierarchy from PPPPP to QCPH⊆BP⋅PP⊆PromiseBPPPP. The same proof also shows PPPromiseBQP=PP. Additionally, we show that PromiseBQP, even when given quantum advice, is self-low under robust queries. Finally, we exhibit an obstruction to transferring language-level counting results to promise classes. Although AWPP and APP are low for PP, a corresponding promise analogue would collapse the counting hierarchy as GapP⊆FPPromiseAWPP. This motivates the introduction of PromisePostBQP∗, which restricts PostBQP to input-indepencent postselection. By showing that it is low for \PP, we obtain PPPromiseYQP∗=PP.
The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis. First, we show that there exists an oracle relation problem (i.e., a problem with many valid outputs) that is solvable in BQP, but not in PH. This also yields a non-oracle relation problem that is solvable in quantum logarithmic time, but not in AC[superscript 0]. Second, we show that an oracle decision problem separating BQP from PH would follow from the Generalized Linial-Nisan Conjecture, which we formulate here and which is likely of independent interest. The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Braverman, after being open for twenty years.