2026-07-26T11:03:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25289 2026-03-19T13:03:02Z ddc:004 open_access

Oracle Separations for the Quantum-Classical Polynomial Hierarchy Agarwal, Avantika Ben{-}David, Shalev Switching Lemma Polynomial Hierarchy Approximate Degree Random Oracles Query Complexity Quantum Computing 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 Q(f) ≤ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avantika Agarwal and Shalev Ben{-}David 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.2 urn:nbn:de:0030-drops-252893 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.2 eng https://creativecommons.org/licenses/by/4.0/legalcode