OP-3008OpenQuantum information

QMA versus QCMA

Determine whether quantum witnesses increase the power of polynomial-time quantum verification: $\mathsf{QMA}\stackrel{?}{=}\mathsf{QCMA}$ , without an oracle.

Source-reported statusAs of 2026-09-04Source & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Determine whether quantum witnesses increase the power of polynomial-time quantum verification: $\mathsf{QMA}\stackrel{?}{=}\mathsf{QCMA}$ , without an oracle.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

QMA allows a polynomial-size quantum witness; QCMA restricts the witness to a classical string while retaining a quantum verifier. The question is whether some efficiently verifiable evidence fundamentally requires quantum information.

What is known: Aaronson–Kuperberg gave a quantum-oracle separation. Natarajan–Nirkhe's distribution-testing separation uses a randomized classical oracle; Ben-David–Kundu's 2024 classical-oracle result restricts adaptivity. These are important intermediate models, not the unrestricted classical-oracle theorem.

The full standard classical-oracle separation is due to Bostanci, Haferkamp, Nirkhe and Zhandry: first posted in November 2025, revised in January 2026 and published at STOC 2026. It strengthens relativized evidence but does not settle the unrelativized QMA versus QCMA question. Related: A4, A5, A10.

Progress & source assessment

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

published: A standard classical oracle separates QMA from QCMA; the unrelativized equality remains open. Evidence

References

[1]Aaronson & Kuperberg, 'Quantum versus classical proofs and advice', Theory of Computing 3 (2007) link
[2]Natarajan & Nirkhe, 'A distribution testing oracle separation between QMA and QCMA', Quantum 8, 1377 (2024) link
[3]Ben-David & Kundu, 'Oracle separation of QMA and QCMA with bounded adaptivity' (2024) link
[4]Bostanci, Haferkamp, Nirkhe & Zhandry, 'A classical oracle separation between QMA and QCMA', STOC 2026 link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.