Two classical oracle separations between QMA and QCMA

Two classical oracle separations between QMA and QCMA

by John Bostanci

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYAMathematical theory of computation
🎙 John Bostanci 👥 75K 📅 July 21, 2026 ⏱ 58 min 👁 505 📄 original study 🧭 2026-08-03
Available in: English (current) Français

Keywords

QMAQCMAoracle separationquantum proofscomplexity theory

Summary

The talk, presented by John Bostanci at the Simons Institute, addresses the longstanding open problem of separating the quantum complexity classes QMA and QCMA. QMA (Quantum Merlin-Arthur) allows quantum proofs, while QCMA (Quantum Classical Merlin-Arthur) restricts proofs to classical strings. The speaker motivates the problem by its connections to quantum cryptography and the difficulty of proving separations without resolving P vs PSPACE. He explains why previous oracle separations were limited, often relying on non-standard oracles or additional assumptions. The main contribution is the construction of two new oracle separations using classical oracles, which are the first of their kind. The talk outlines the shared proof strategy, which involves a ‘fisherman’ parable to illustrate the lower bound technique, and then highlights the differences between the two constructions. The first oracle uses a problem based on the Local Hamiltonian, while the second employs a more structured oracle to overcome technical challenges. The speaker emphasizes the importance of these results as evidence that QMA and QCMA are distinct, and as a step toward understanding the power of quantum proofs. The talk concludes with open questions and potential future directions.

186 words

Critical Evaluation

The talk presents a significant breakthrough in quantum complexity theory: the first classical oracle separations between QMA and QCMA. The speaker, John Bostanci, demonstrates deep expertise and communicates complex ideas with clarity. The motivation is well-articulated, connecting the problem to quantum cryptography and the broader challenge of separating quantum and classical proofs. The technical content is rigorous, with the speaker carefully explaining the proof strategy and the difficulties overcome. The use of the ‘fisherman’ parable is an effective pedagogical tool, making the lower bound argument intuitive. The talk is well-structured, first outlining the shared framework and then detailing the two distinct oracle constructions. The speaker acknowledges prior work and situates the new results within the existing literature. However, as a conference talk, the presentation necessarily omits full technical details and formal proofs, which are presumably available in the associated paper. The speaker does not explicitly mention the paper’s availability, but the talk is based on original research. The adequacy between title and content is excellent: the talk indeed presents two classical oracle separations. The main limitation is the lack of peer-reviewed publication details, but the technical depth and clarity suggest high reliability. Overall, this is an excellent talk that will be of great interest to researchers in quantum complexity theory.

210 words

Title / Content Match

The title accurately reflects the content: the talk presents two new oracle separations between QMA and QCMA.

Quality & Reliability

8/10

Talk by a researcher presenting original results, with technical depth and references to prior work. The presentation is clear and rigorous, but as a conference talk, it lacks full proofs and peer-reviewed details.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

This talk presents two new oracle separations between QMA and QCMA, which are the first to use classical oracles. This is a significant advance over previous work that relied on non-standard oracles or additional assumptions. The results provide strong evidence that QMA and QCMA are distinct complexity classes, and they offer new techniques for separating quantum and classical proofs. The talk also highlights connections to quantum cryptography, as the oracle constructions incorporate properties like non-clonability and non-collapsing hash functions.

Pour aller plus loin :

  • QMA (complexity) — Background on the complexity class QMA.
  • QCMA (complexity) — Background on the complexity class QCMA.
  • Oracle machine — Definition and role of oracles in complexity theory.
  • Local Hamiltonian problem — The problem used in the first oracle construction.
  • Quantum cryptography — Connections to quantum cryptographic primitives.

133 words

Radar Profile

The radar profile shows high scores in technical level and information quality, reflecting the advanced and rigorous nature of the talk. The lower score in quantity of information is due to the talk's focus on a specific result rather than a broad overview. Overall, the profile indicates a highly specialized and reliable presentation.

Reliability 8/10