2026-07-22T16:11:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26492 2026-07-01T07:16:12Z ddc:004 open_access

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity Grewal, Sabee Rudolph, Dorian quantum complexity theory quantum polynomial hierarchy pure quantum polynomial hierarchy QPH QMA(2) quantum proof systems interactive proofs quantified Hamiltonian complexity local Hamiltonian problem sparse Hamiltonians disentanglers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sabee Grewal and Dorian Rudolph 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.103 urn:nbn:de:0030-drops-264922 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.103 eng https://creativecommons.org/licenses/by/4.0/legalcode