Breakthrough Tracker record
Separating QMA from QCMA with a classical oracle
The authors constructed a classical-oracle setting in which QMA, the class with quantum witnesses, is strictly larger than QCMA, whose witnesses are classical. The proof uses a decision problem called spectral Forrelation.
← Back to the filtered Breakthrough Tracker
- Stable ID
qma-qcma-classical-oracle-2026- Revision
qma-qcma-classical-oracle-2026.v1- Field
- Computer Science · Quantum complexity theory
- Evidence
- Tier 1 · Peer reviewed: Yes
- Record state
- Current · Verified/published conference result
- Last checked
AI role
No AI assistance was disclosed in the paper or linked reporting.
Record details
- Problem or result
- Whether quantum proofs can be strictly more powerful than classical proofs checked by a quantum verifier
- Authors
- John Bostanci, Jonas Haferkamp, Chinmay Nirkhe and Mark Zhandry
- Institutions
- Columbia, Saarland/Harvard, University of Washington, Stanford and NTT Research
- Result date
- November 12, 2025; published at STOC 2026 on June 9, 2026
Why it matters
It supplies the oracle separation quantum-complexity researchers had sought for roughly two decades and introduces techniques that may be useful beyond this problem.
Limits
This is a relativized oracle separation, not an unconditional proof that QMA differs from QCMA in the ordinary unrelativized setting. It is not a demonstrated hardware advantage.
Sources
- Primary: Final ACM STOC 2026 proceedings record
- Primary: Primary paper on arXiv
- Primary: Author publication record confirming STOC 2026 Best Paper
- Independent: Quanta Magazine explanation
- Independent: Ruhr University report on the STOC Best Paper Award
Correction and revision history
- July 22, 2026 — Added the final ACM STOC 2026 proceedings record and changed “accepted” to “published.” The theorem statement and verification status are unchanged.
Machine-readable: JSON v1 · CSV v1 · Schema v1
This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.