Quantum-Classical Merlin-Arthur

Also written MQA (Merlin Quantum Arthur): the class of decision problems verifiable by a protocol where Merlin sends a classical proof string, but Arthur is a polynomial-time quantum algorithm. Formally, a language $L\in \mathbf{QCMA}$ if there exists a polynomial-time quantum verifier $V$ and polynomials $p,q$ such that:

1. If $x\in L$, there exists a classical string $w\in \{0,1{\}}^{p(|x|)}$ such that $V$ accepts $(x,w)$ with probability at least 2/3.
2. If $x\notin L$, then for all $w\in \{0,1{\}}^{p(|x|)}$, $V$ rejects $(x,w)$ with probability at least 2/3.

QCMA sits between MA (classical verifier) and QMA (quantum witness allowed) in the hierarchy of proof systems.

See the complexity zoo entry here.

Known relationships

• $\mathbf{MA}\subseteq \mathbf{QCMA}\subseteq \mathbf{QMA}$: any MA protocol is a QCMA protocol (ignore the quantum capabilities of the verifier); any QCMA protocol is a QMA protocol (quantum states can encode classical strings).
• $\mathbf{QCMA}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}$, since $\mathbf{QMA}\subseteq \mathbf{PP}$ — MW05.

Oracle separation from QMA

Relative to oracles, $\mathbf{QMA}⊈\mathbf{QCMA}$ (no-qcma-to-qma-ak07):

• AK07: relative to a quantum unitary oracle; also separates $\mathbf{BQP}/\mathrm{qpoly}$ from $\mathbf{BQP}/\mathrm{poly}$ relative to a quantum oracle.
• BFM23: relative to an in-place quantum oracle, for a graph connectivity problem, via representation theory of the symmetric group.
• NN23: relative to a distributional classical oracle (connectivity of a random graph), with the honest quantum witness depending only on the oracle distribution, not the sampled oracle.
• BK24: relative to a standard classical oracle, for verifiers of bounded adaptivity (polynomially many queries per round, few rounds).
• BHNZ25: relative to a standard classical oracle, with no restriction, via spectral Forrelation.
• BHV26: a simpler proof of the BHNZ25 separation via good error-correcting codes; also the first classical-oracle separation of $\mathbf{BQP}/\mathrm{qpoly}$ from $\mathbf{BQP}/\mathrm{poly}$.

All of these are oracle separations; whether $\mathbf{QCMA}=\mathbf{QMA}$ holds in the unrelativized world remains open.

Relevance to cryptography

The QCMA vs QMA question captures whether quantum witnesses are inherently more useful than classical ones for quantum verifiers. In the context of zero-knowledge proofs:

• A QCMA-complete problem has a classical proof that a quantum verifier can check, which is useful for constructing quantum zero-knowledge protocols with classical proofs.
• If QMA = QCMA (in the unrelativized world), quantum witnesses provide no extra power — simplifying the design of post-quantum proof systems. The oracle separations make this unlikely.

Participates in

Builds on Quantum-Classical Merlin-Arthur

• QCMA ⊆ QMA

Produces Quantum-Classical Merlin-Arthur

• MA ⊆ QCMA

Barriers

• No relativizing reduction from QMA to QCMA