2026-07-21T12:17:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22723 2026-04-17T05:32:48Z ddc:004 open_access

Toward Separating QMA from QCMA with a Classical Oracle Zhandry, Mark Quantum Oracle Separations QMA QCMA QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark Zhandry 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.95 urn:nbn:de:0030-drops-227230 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.95 eng https://creativecommons.org/licenses/by/4.0/legalcode