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}$.

Oracle separation from QMA

The question of whether $\mathbf{QCMA}=\mathbf{QMA}$ — i.e., whether quantum proofs are strictly more powerful than classical proofs for quantum verifiers — was resolved in the oracle model through a sequence of increasingly general results:

• No reduction from QCMA to QMA
• No reduction from QCMA to QMA
• No reduction from QCMA to QMA
• No reduction from QCMA to QMA
• No reduction from QCMA to QMA
• No reduction from QCMA to QMA

Note that 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 ⊆ PP
• QCMA ⊆ QMA

Produces Quantum-Classical Merlin-Arthur

• MA ⊆ QCMA

Barriers

• No reduction from QCMA to QMA