2026-08-18T13:22:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20563 2024-08-23T05:50:28Z ddc:004 open_access

Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds Agarwal, Avantika Gharibian, Sevag Koppula, Venkata Rudolph, Dorian Quantum complexity polynomial hierarchy 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 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 (QPHpure) 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 QPHpure, we show one-sided error reduction QPHpure, as well as the first bounds relating these quantum variants of PH, namely QCPH ⊆ QPHpure ⊆ EXP^PP. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avantika Agarwal and Sevag Gharibian and Venkata Koppula and Dorian Rudolph 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.7 urn:nbn:de:0030-drops-205632 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode