Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 67 / 3 / a

A promise problem $(L_{\mathrm{yes}},L_{\mathrm{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 thatNo 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.