Quantum Merlin-Arthur

The quantum analogue of MA: Merlin (an unbounded prover) sends a polynomial-size quantum state as a proof to Arthur (a polynomial-time quantum verifier), who then performs a quantum measurement to decide whether to accept. We require:

1. If the answer is “yes,” there exists a quantum state Merlin can send such that Arthur accepts with probability at least 2/3.
2. If the answer is “no,” for every quantum state Merlin might send, Arthur rejects with probability at least 2/3.

QMA is the quantum analogue of NP (with a quantum verifier and quantum witness), just as MA is the probabilistic analogue of NP.

See the complexity zoo entry here.

Notable problems

• Local Hamiltonian (k-LH): given a $k$-local Hamiltonian $H={\sum }_i{H}_i$ on $n$ qubits with $\mathrm{poly}(n)$ terms, each of norm at most $\mathrm{poly}(n)$, and thresholds $a<b$ with $b-a\ge 1/\mathrm{poly}(n)$, decide whether the ground-state energy of $H$ is at most $a$ or at least $b$, promised one holds. This is QMA-complete for $k\ge 2$ — KKR06 (for $k\ge 5$ first by Kitaev — KSV02). The Local Hamiltonian problem is the quantum analogue of SAT.
• Consistency of local density matrices: given density matrices ${\rho }_1,\dots ,{\rho }_m$ on subsets $C_1,\dots ,C_m$ of at most $k$ of $n$ qubits, decide whether some $n$-qubit state $\sigma$ has every reduced state ${\mathrm{Tr}}_{\overline{C_i}}(\sigma )$ within trace distance $\beta$ of ${\rho }_i$, or every $n$-qubit state $\sigma$ has some reduced state ${\mathrm{Tr}}_{\overline{C_i}}(\sigma )$ at trace distance at least $\alpha$ from ${\rho }_i$, where $\alpha -\beta \ge 1/\mathrm{poly}(n)$. In QMA and QMA-hard under Turing reductions — Liu06; QMA-hard under Karp reductions — BG20.

Known relationships

• $\mathbf{NP}\subseteq \mathbf{MA}\subseteq \mathbf{QCMA}\subseteq \mathbf{QMA}$: classical proofs can be checked classically, classically by a quantum machine, or quantumly by a quantum machine.
• $\mathbf{QMA}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}$: first proved as $\mathbf{QMA}\subseteq {\mathrm{A}}_0\mathrm{PP}$ — Vya03 (stated earlier without proof in KW00); a short proof via strong error reduction is in MW05; see qma-to-pp.
• QMA is closed under intersection: run both error-reduced verifiers (MW05), each on its own witness register, and accept iff both accept — folklore. Closure under complement — i.e., whether $\mathbf{QMA}=\mathbf{coQMA}$ — is open, analogous to the classical question of $\mathbf{MA}$ vs $\mathbf{coMA}$.
• $\mathbf{QMA}$ and $\mathbf{AM}$ are believed incomparable.
• QMA(2): the class with two unentangled quantum proofs is believed strictly more powerful than QMA. $\mathbf{QMA}(2)\subseteq \mathbf{NEXP}$ (guess classical descriptions of both proofs and compute the acceptance probability) — folklore; whether $\mathbf{QMA}(2)\subseteq \mathbf{EXP}$ is open.

Variants

Recent work has studied how modifications to the proof model change QMA’s power:

• QMA+ (proofs with non-negative amplitudes): restricting quantum proofs to have non-negative amplitudes (no relative phase between basis states) dramatically changes the class. With one constant completeness-soundness gap, $\mathbf{QMA}+=\mathbf{NEXP}$; with a different gap, $\mathbf{QMA}+=\mathbf{QMA}$ — BFM24. One interpretation is that Merlin’s ability to cheat comes from relative phase at least as much as from entanglement, since $\mathbf{QMA}(2)\subseteq \mathbf{NEXP}$ — BFM24.
• QMA with a non-collapsing measurement: if the verifier may apply a single measurement that does not disturb the quantum state (a “non-collapsing” measurement), then QMA equals NEXP — BM25, resolving an open question of Aaronson.
• QMA with internally separable proofs: a variant where each proof must be “internally separable” (after tracing out one register, a small number of qubits are separable from the rest): ${\mathbf{QMA}}_{\mathrm{IS}}\subseteq \mathbf{EXP}$ but ${\mathbf{QMA}}_{\mathrm{IS}}(2)=\mathbf{NEXP}$, so one such proof is strictly weaker than two unentangled ones unless EXP $=$ NEXP — BFL+24. This provides a new route toward proving QMA(2) = NEXP.

Relevance to cryptography

For every $\gamma \ge 1$, the gap shortest vector problem ${\mathrm{GapSVP}}_{\gamma }$ is in $\mathbf{NP}\subseteq \mathbf{QMA}$, since a short vector is a classical witness — folklore. For $\gamma \ge \sqrt{n}$, ${\mathrm{GapSVP}}_{\gamma }\in \mathbf{NP}\cap \mathbf{coNP}$ — AR04, so it is not QMA-hard under Karp reductions unless $\mathbf{QMA}\subseteq \mathbf{NP}\cap \mathbf{coNP}$.

Participates in

Builds on Quantum Merlin-Arthur

• Local Hamiltonian is QMA-complete (via Notable problems)
• QMA ⊆ PP

Produces Quantum Merlin-Arthur

• Local Hamiltonian is QMA-complete
• QCMA ⊆ QMA

Barriers

• No relativizing reduction from QMA to QCMA