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:2401.01633 · Leibniz international proceedings in informatics

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

Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph

Published Jan 1, 2024• 9 citations
arXivHTMLPDF

Abstract

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

DOI
10.4230/lipics.mfcs.2024.7

Related papers

Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2)

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

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

•Jan 1, 2018•1 citation

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•25 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•6 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•1 citation

Nonuniform QCPH Collapse Implies QCPH Collapse

Jeremy Ahrens Huang

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.

cs.CCCross-listedarXiv:2610.04423•Oct 6, 2026•0 citations

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity

Sabee Grewal, Dorian Rudolph

We prove several new results concerning the pure quantum polynomial hierarchy pureQPH. First, we show that QMA(2) ⊆ pureQΣ_2, i.e., two unentangled existential provers can be simulated by competing existential and universal provers. We further prove that pureQΣ_2 ⊆ QΣ_3 ⊆ NEXP. Second, we give an error reduction result for pureQPH, and, as a consequence, prove that pureQPH = QPH. A key ingredient in this result is an improved dimension-independent disentangler. Finally, we initiate the study of quantified Hamiltonian complexity, the quantum analogue of quantified Boolean formulae. We prove that the quantified pure sparse Hamiltonian problem is pureQΣ_i-complete. By contrast, other natural variants (pure/local, mixed/local, and mixed/sparse) admit nontrivial containments but fail to be complete under known techniques. For example, we show that the ∃∀-mixed local Hamiltonian problem lies in NP^QMA ∩ coNP^QMA.

arXiv:2510.06522•Leibniz international proceedings in informatics•Oct 7, 2025•1 citation
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-time hierarchy (PH\mathrm{PH}PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH\mathrm{PH}PH does not collapse). Here, we study whether two quantum generalizations of PH\mathrm{PH}PH can similarly prove separations in the quantum setting. The first generalization, QCPH\mathrm{QCPH}QCPH, uses classical proofs, and the second, QPH\mathrm{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\mathrm{Q} \Sigma_3QΣ3​, into NEXP\mathrm{NEXP}NEXP {using the Ellipsoid Method for efficiently solving semidefinite programs}. These results yield two implications for QMA(2)\mathrm{QMA}(2)QMA(2), the variant of Quantum Merlin-Arthur (QMA\mathrm{QMA}QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH\mathrm{QCPH} = \mathrm{QPH}QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then QMA(2)\mathrm{QMA}(2)QMA(2) is in the Counting Hierarchy (specifically, in PPPPP\mathrm{P}^{\mathrm{PP}^{\mathrm{PP}}}PPPPP). Second, unless QMA(2)=QΣ3\mathrm{QMA}(2)={\mathrm{Q} \Sigma_3}QMA(2)=QΣ3​ (i.e., alternating quantifiers do not help in the presence of "unentanglement"), QMA(2)\mathrm{QMA}(2)QMA(2) is strictly contained in NEXP\mathrm{NEXP}NEXP.
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'').
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.
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.
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.
We prove several new results concerning the pure quantum polynomial hierarchy pureQPH. First, we show that QMA(2) ⊆ pureQΣ_2, i.e., two unentangled existential provers can be simulated by competing existential and universal provers. We further prove that pureQΣ_2 ⊆ QΣ_3 ⊆ NEXP. Second, we give an error reduction result for pureQPH, and, as a consequence, prove that pureQPH = QPH. A key ingredient in this result is an improved dimension-independent disentangler. Finally, we initiate the study of quantified Hamiltonian complexity, the quantum analogue of quantified Boolean formulae. We prove that the quantified pure sparse Hamiltonian problem is pureQΣ_i-complete. By contrast, other natural variants (pure/local, mixed/local, and mixed/sparse) admit nontrivial containments but fail to be complete under known techniques. For example, we show that the ∃∀-mixed local Hamiltonian problem lies in NP^QMA ∩ coNP^QMA.