[BK24] Oracle Separation of QMA and QCMA with Bounded Adaptivity

Authors: Shalev Ben-David, Srijita Kundu | Venue: ICALP 2024 | Source

Abstract

We achieve an oracle separation between QMA and QCMA relative to a standard classical oracle, under the restriction that the quantum algorithms make queries with bounded adaptivity (polynomially many queries per round, but few rounds). This simplifies the construction of Li–Liu–Pelecanos–Yamakawa and introduces the notion of “slippery” relations as a technical tool. While falling short of a fully adaptive separation, this work is a key step toward the complete classical oracle separation that was subsequently achieved in [BHNZ25].