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

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

Miklós Sántha, Sevag Gharibian, Jamie Sikora, Aarthi Sundaram, Justin Yirka

Published Jan 1, 2018• 0 citations
OpenAlex

Abstract

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

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

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

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

QMA variants with polynomially many provers

Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay

We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly \class{MQA} (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class $\class{BellQMA}(\poly)$, characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly \class{QMA}. Finally, we study a class equivalent to \class{QMA}($m$), denoted $\class{SepQMA}(m)$, where the verifier's measurement operator corresponding to outcome {\it accept} is a fully separable operator across the $m$ quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for $\class{SepQMA}(m)$ for any $m$.

Quantum Information and Computation•Jan 1, 2013•17 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•0 citations

QMA variants with polynomially many provers

Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay

We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly MQA (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class BellQMA(poly), characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly QMA. Finally, we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's measurement operator corresponding to outcome "accept" is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for SepQMA(m) for any m.

arXiv:1108.0617•Aug 2, 2011•2 citations
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-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.
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.
We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly \class{MQA} (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class $\class{BellQMA}(\poly)$, characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly \class{QMA}. Finally, we study a class equivalent to \class{QMA}(mmm), denoted $\class{SepQMA}(m)$, where the verifier's measurement operator corresponding to outcome {\it accept} is a fully separable operator across the mmm quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for $\class{SepQMA}(m)$ for any mmm.
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.
We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size, is exactly MQA (also known as QCMA), the class of problems which can be efficiently verified via a classical proof and a quantum verifier. We then study the class BellQMA(poly), characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly QMA. Finally, we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's measurement operator corresponding to outcome "accept" is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, pp. 633--642 (2010)] that shows a perfect parallel repetition theorem for SepQMA(m) for any m.