2026-07-24T17:52:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20164 2024-07-02T07:52:49Z ddc:004 open_access

Oracle Separation of QMA and QCMA with Bounded Adaptivity Ben-David, Shalev Kundu, Srijita Quantum computing computational complexity We give an oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries; that is, the number of rounds of oracle calls is small, though each round may involve polynomially many queries in parallel. Our oracle construction is a simplified version of the construction used recently by Li, Liu, Pelecanos, and Yamakawa (2023), who showed an oracle separation between QMA and QCMA when the quantum algorithms are only allowed to access the oracle classically. To prove our results, we introduce a property of relations called slipperiness, which may be useful for getting a fully general classical oracle separation between QMA and QCMA. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shalev Ben-David and Srijita Kundu 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.21 urn:nbn:de:0030-drops-201642 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.21 eng https://creativecommons.org/licenses/by/4.0/legalcode