QMA versus QCMA

A proposed solution can be easier to check than to discover. For the switch rule “x or y must be on,” the two bits “x on, y off” are a certificate: a checker can directly confirm the rule. QMA versus QCMA asks whether some questions need a different kind of certificate—a quantum state, which a quantum computer can process and measure—rather than a short list of ordinary bits. In both cases the checker is a quantum computer. The unknown is whether quantum evidence lets it verify any additional problems efficiently, without extra access to a special answer-giving device.[1]

Are there families of problems whose yes answers have short quantum certificates, but which no efficient quantum verifier can check using only short classical certificates? For “x or y must be on,” the assignment $x=1,y=0$ is easily checked; this is a common certificate example, not evidence of a quantum advantage. The class comparison concerns families of promise problems: inputs are promised to belong to disjoint yes and no sets, and intermediate inputs need not be classified. A verifier receives the classical input $x$ and a witness of length polynomial in $|x|$, the input’s bit length. It runs a uniformly generated quantum circuit of polynomial size and finally accepts or rejects. In $\mathrm{QCMA}$, the witness is a bit string; in $\mathrm{QMA}$, it is a state of polynomially many qubits. For each yes input, some witness must be accepted with probability at least $2/3$; for each no input, every witness must be accepted with probability at most $1/3$. Quantum verification can process a bit string as a quantum state encoding those same 0/1 bits, giving $\mathrm{QCMA}\subseteq\mathrm{QMA}$. The question is equality for ordinary computation. An oracle is extra access to a specified function; adding the same oracle to both verifiers changes the model.[1]

The comparison in ordinary computation remains open.[1]

STOC 2026 gives a separation after adding a classical oracle. That result resolves the stated oracle variant, not the unrelativized class comparison.[1]

Being able to check an answer gives another person a way to trust it without reproducing the entire search. This question asks whether that evidence can always be communicated as ordinary bits when the checker already has quantum computing power. A quantum certificate is supplied as a physical state; a classical certificate is a string that can be copied and stored. Their comparison isolates the value of the evidence itself, rather than the value of switching to a faster checker.[1]

The comparison separates the complexity of checking a fact from the form of the evidence used to check it. A quantum witness may help through the results of quantum operations and measurements, rather than through a complete numerical description of the state. Equality would require suitable classical evidence, possibly entirely different from that numerical description, for every QMA promise problem. An oracle separation demonstrates a setting where quantum evidence is essential, but leaves open whether the structure of ordinary, explicitly described inputs provides a classical route to verification.[1]