Toward separating QMA from QCMA with a classical oracle

DOI10.4230/LIPICS.ITCS.2025.95MaRDI QIDQ7296743zbMATH OpenFDO

Authors Mark Zhandry

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.95

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A distribution testing oracle separating QMA and QCMA
• Classical vs quantum advice and proofs under classically-accessible oracle
• Non-uniformity and quantum advice in the quantum random oracle model
• Probability inequalities for the sum in sampling without replacement
• Quantum time-space tradeoff for finding multiple collision pairs
• Quantum vs. classical proofs and subset verification
• Secure identity-based encryption in the quantum random oracle model
• Strengths and Weaknesses of Quantum Computing
• Verifiable quantum advantage without structure

Cited in

(1)

• Generalised linial-nisan conjecture is false for DNFs

This page was built for publication: Toward separating QMA from QCMA with a classical oracle

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