Oracle separation of QMA and QCMA with bounded adaptivity

DOI10.4230/LIPICS.ICALP.2024.21MaRDI QIDQ6875188zbMATH OpenFDO

Authors Shalev Ben-David, Srijita Kundu

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.21

zbMATH Keywords

computational complexityquantum computing

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A distribution testing oracle separating QMA and QCMA
• A qubit, a coin, and an advice string walk into a relational problem
• Classical vs quantum advice and proofs under classically-accessible oracle
• Non-uniformity and quantum advice in the quantum random oracle model
• On the power of nonstandard quantum oracles
• Oracle separation of BQP and PH
• Quantum vs. classical proofs and subset verification
• Query-to-communication lifting for BPP
• Random oracles and non-uniformity
• Strengths and Weaknesses of Quantum Computing
• Verifiable quantum advantage without structure

Cited in

(1)

• The role of piracy in quantum proofs

This page was built for publication: Oracle separation of QMA and QCMA with bounded adaptivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875188)