Math Conjectures

QMA versus QCMA

OPENMajorOpen problemProposed 2002 · Standard version

Canonical statement

Does QMA=QCMA\mathsf{QMA}=\mathsf{QCMA}? The class QMA\mathsf{QMA} uses a polynomial-time quantum verifier with a polynomial-size quantum witness and bounded completeness and soundness error; QCMA\mathsf{QCMA} restricts the witness to a classical bit string.
View source LaTeX
Does \(\mathsf{QMA}=\mathsf{QCMA}\)? The class \(\mathsf{QMA}\) uses a polynomial-time quantum verifier with a polynomial-size quantum witness and bounded completeness and soundness error; \(\mathsf{QCMA}\) restricts the witness to a classical bit string.
TCS-QUANT-032:[AharonovNaveh2002QuantumNP][AaronsonKuperberg2007ProofsAdvice][BostanciHaferkampNirkheZhandry2026Oracle][BostanciHuangVaikuntanathan2026Codes]
Theoretical computer scienceLogic and foundations

Notes

QMA consists of decision problems having polynomial-size quantum witnesses verified in quantum polynomial time with bounded error, while QCMA restricts the witness to a classical bit string. Their standard complexity-theoretic formulation was developed in the early study of quantum NP [AharonovNaveh2002QuantumNP]. Since a classical witness is a special case of a quantum one, QCMA⊆QMA\mathrm{QCMA}\subseteq\mathrm{QMA}; strictness is a common expectation, but the canonical problem neutrally asks whether equality holds.

Aaronson and Kuperberg constructed a quantum oracle relative to which QMA differs from QCMA, demonstrating a genuine quantum-witness advantage in a relativized model [AaronsonKuperberg2007ProofsAdvice]. Such a quantum-oracle separation cannot settle the ordinary, unrelativized classes.

Recent work gives classical-oracle separations through two complementary constructions [BostanciHaferkampNirkheZhandry2026Oracle] [BostanciHuangVaikuntanathan2026Codes]. These advances rule out broad classes of relativizing proof techniques, but they still leave the main question open: no explicit unrelativized language is known to lie in QMA but outside QCMA, and no simulation proves equality.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.