Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.04423

Nonuniform QCPH Collapse Implies QCPH Collapse

Jeremy Ahrens Huang

cs.CCquant-phSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
8 pages

Related papers

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

Sevag Gharibian, Miklós Sántha, Jamie Sikora +2 more

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'').

arXiv:1805.11139•Computational Complexity•Sep 20, 2022•11 citations

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy

Kartik Anand, Kabgyun Jeong, Junseo Lee

We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not reduce computational power: $\mathsf{UniqueQCPCP} = \mathsf{QCPCP}$ under $\mathsf{BQ}$-operator and randomized reductions, demonstrating robustness similar to the $\mathsf{UniqueQCMA} = \mathsf{QCMA}$ result. Second, we establish a non-uniform quantum analogue of the Karp-Lipton theorem, showing that if $\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}$, then $\mathsf{QPH} \subseteq \mathsf{QΣ}_2/\mathsf{qpoly}$, extending the classical collapse theorem to quantum complexity with quantum advice. Third, we introduce a consistent variant of the quantum polynomial hierarchy ($\mathsf{CQPH}$) with consistency constraints across interaction rounds while maintaining product-state proofs, proving its unconditional collapse $\mathsf{CQPH} = \mathsf{CQΣ}_2$. This contrasts with prior work on quantum-entangled polynomial hierarchy, showing that consistency rather than entanglement drives the collapse. These results contribute to understanding structural boundaries in quantum complexity theory and the interplay between constraint types in quantum proof systems.

arXiv:2506.19792•Jun 24, 2025•0 citations

Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds

Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1 more

The Polynomial-Time Hierarchy ($\mathsf{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 $\mathsf{PH}$ exist, it has been challenging to prove analogues for these of even basic facts from $\mathsf{PH}$. This work studies three quantum-verifier based generalizations of $\mathsf{PH}$, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings ($\mathsf{QCPH}$) and quantum mixed states ($\mathsf{QPH}$) as proofs, and one of which is new to this work, utilizing quantum pure states ($\mathsf{pureQPH}$) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for $\mathsf{QCPH}$. Then, for our new class $\mathsf{pureQPH}$, we show one-sided error reduction for $\mathsf{pureQPH}$, as well as the first bounds relating these quantum variants of $\mathsf{PH}$, namely $\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}$.

arXiv:2401.01633•Leibniz international proceedings in informatics•Jan 1, 2024•0 citations

A Collapsible Polynomial Hierarchy for Promise Problems

Chirag Falor, Shu Ge, Anand Natarajan

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.

arXiv:2311.12228•Nov 20, 2023•0 citations

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Marshall, Simon C., Scott Aaronson, Dunjko, Vedran

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP = PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling, IQP, DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment’s hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠ FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPP^NP.

•Jan 1, 2025•0 citations

Oracle Separations for the Quantum-Classical Polynomial Hierarchy

Avantika Agarwal, Shalev Ben-David

We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that for any $d$, if we apply a random restriction to a function $f$ with quantum query complexity $\mathrm{Q}(f)\le n^{1/3}$, the restricted function becomes exponentially close (in terms of $d$) to a depth-$d$ decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.

arXiv:2410.19062•Leibniz international proceedings in informatics•Oct 24, 2024•0 citations
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\rm{QCPH}QCPH , uses classical proofs, and the second, QPH\rm{QPH}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\rm{Q\Sigma_3}QΣ3​ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for QMA(2)\rm{QMA(2)}QMA(2) , the variant of Quantum Merlin-Arthur ( QMA\rm{QMA}QMA ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH\rm{QCPH = QPH}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{\rm P}^{{\rm pp}^{{\rm pp}}}Ppppp ). Second, because QMA(2)⊆QΣ3\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}QMA(2)⊆QΣ3​ , QMA(2)\rm{QMA(2)}QMA(2) is strictly contained in NEXP unless QMA(2)=QΣ3\rm{QMA(2)}=\rm{Q\Sigma_3}QMA(2)=QΣ3​ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').
We investigate structural properties of quantum proof systems by establishing collapse results that uncover simplifications in their complexity landscape. We extend classical results such as the Karp-Lipton theorem to quantum polynomial hierarchy with quantum proofs and establish uniqueness preservation for quantum-classical probabilistically checkable proof systems. Our main contributions are threefold. First, we prove that restricting quantum-classical PCP systems to uniqueness does not reduce computational power: UniqueQCPCP=QCPCP\mathsf{UniqueQCPCP} = \mathsf{QCPCP}UniqueQCPCP=QCPCP under BQ\mathsf{BQ}BQ-operator and randomized reductions, demonstrating robustness similar to the UniqueQCMA=QCMA\mathsf{UniqueQCMA} = \mathsf{QCMA}UniqueQCMA=QCMA result. Second, we establish a non-uniform quantum analogue of the Karp-Lipton theorem, showing that if QMA⊆BQP/qpoly\mathsf{QMA} \subseteq \mathsf{BQP}/\mathsf{qpoly}QMA⊆BQP/qpoly, then QPH⊆QΣ2/qpoly\mathsf{QPH} \subseteq \mathsf{QΣ}_2/\mathsf{qpoly}QPH⊆QΣ2​/qpoly, extending the classical collapse theorem to quantum complexity with quantum advice. Third, we introduce a consistent variant of the quantum polynomial hierarchy (CQPH\mathsf{CQPH}CQPH) with consistency constraints across interaction rounds while maintaining product-state proofs, proving its unconditional collapse CQPH=CQΣ2\mathsf{CQPH} = \mathsf{CQΣ}_2CQPH=CQΣ2​. This contrasts with prior work on quantum-entangled polynomial hierarchy, showing that consistency rather than entanglement drives the collapse. These results contribute to understanding structural boundaries in quantum complexity theory and the interplay between constraint types in quantum proof systems.
The Polynomial-Time Hierarchy (PH\mathsf{PH}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\mathsf{PH}PH exist, it has been challenging to prove analogues for these of even basic facts from PH\mathsf{PH}PH. This work studies three quantum-verifier based generalizations of PH\mathsf{PH}PH, two of which are from [Gharibian, Santha, Sikora, Sundaram, Yirka, 2022] and use classical strings (QCPH\mathsf{QCPH}QCPH) and quantum mixed states (QPH\mathsf{QPH}QPH) as proofs, and one of which is new to this work, utilizing quantum pure states (pureQPH\mathsf{pureQPH}pureQPH) as proofs. We first resolve several open problems from [GSSSY22], including a collapse theorem and a Karp-Lipton theorem for QCPH\mathsf{QCPH}QCPH. Then, for our new class pureQPH\mathsf{pureQPH}pureQPH, we show one-sided error reduction for pureQPH\mathsf{pureQPH}pureQPH, as well as the first bounds relating these quantum variants of PH\mathsf{PH}PH, namely QCPH⊆pureQPH⊆EXPPP\mathsf{QCPH}\subseteq \mathsf{pureQPH} \subseteq \mathsf{EXP}^{\mathsf{PP}}QCPH⊆pureQPH⊆EXPPP.
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.
This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP = PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling, IQP, DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment’s hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠ FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPP^NP.
We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that for any ddd, if we apply a random restriction to a function fff with quantum query complexity Q(f)≤n1/3\mathrm{Q}(f)\le n^{1/3}Q(f)≤n1/3, the restricted function becomes exponentially close (in terms of ddd) to a depth-ddd decision tree. Our switching lemma works even in a "worst-case" sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.