= Solution
A <promise problem> $(L_{\rm yes},L_{\rm no})$ belongs to <QMA> if there are polynomials $p,q$ and a uniform family of <quantum circuits> $V_x$ of size at most $q(|x|)$, taking a $p(|x|)$-qubit witness and clean ancillas, with one output qubit interpreted as acceptance, such that
$$
\boxed{\begin{aligned}
x\in L_{\rm yes}&\Longrightarrow
\exists\rho:\ \Pr[V_x\text{ accepts }\rho]\geq\frac23,\\
x\in L_{\rm no}&\Longrightarrow
\forall\rho:\ \Pr[V_x\text{ accepts }\rho]\leq\frac13.
\end{aligned}}
$$
No condition is imposed outside the promise. The witness may be an arbitrary <density operator>, and the verifier is efficient but need not know how to prepare an honest witness. Pure witnesses suffice for completeness because the acceptance probability is linear in the witness. <QMA> is quantum verification with polynomially many witness <qubits> and a constant completeness-soundness gap.
Back to article page
