QMA

QMA is the class of promise problems with a polynomial-size quantum witness checked by a uniform polynomial-size quantum circuit. YES instances have an accepting witness with probability at least $2/3$; NO instances have acceptance at most $1/3$ for every witness, including mixed states. The verifier's acceptance is linear in the witness density operator. Inverse-polynomial or exponentially small error can be obtained through QMA error reduction.

For quantum witness embedding $J$, verifier unitary $U$ and accepting projector $\Pi$, the witness acceptance operator is the positive contraction $F=J^{†}{U}^{†}\Pi UJ$. The maximum acceptance over normalized quantum witnesses is ${\lambda }_{\max }(F)$ by the Rayleigh quotient. Restricting to basis quantum witnesses only tests its diagonal entries and need not find that maximum.

For a positive witness acceptance operator on dimension $D$, large trace powers approximate its largest eigenvalue. With an $m$-qubit QMA quantum witness and $d=2m+2$, the usual NO instances give $\mathrm{Tr}(F^d)<2^{-d}$ and YES instances give a value above $2^{-d}$. A closed product-index expansion computes the trace by recomputation with polynomial storage, avoiding logarithms and roots in a real-arithmetic implementation.

Starting from completeness $2/3$ and soundness $1/3$, run an odd number $r$ of parallel copies and take majority. The QMA parallel repetition with entangled witnesses argument proves soundness for arbitrary repeated witnesses. Exponential Markov's inequality gives majority error at most $(2\sqrt{2}/3{)}^r$. Hence $O(\log (1/ϵ))$ copies suffice for error $ϵ$, with polynomial overhead when the target error is inverse-polynomial or exponentially small in input length.

Independent verifier circuits on $r$ witness registers induce a threshold acceptance effect built from tensor products of $M$ and $I-M$, where $M$ is the quantum verifier acceptance operator. In a product eigenbasis of $M$, the effect's eigenvalues are threshold probabilities for independent Bernoulli random variables with parameters given by the selected eigenvalues of $M$. Bounding every parameter on a NO instance bounds the effect's operator norm, even if the actual submitted witness is entangled. Independence is used only for the spectral calculation, not assumed for the witness.

A verifier with clean ancillas and a designated output measurement induces an effect $0\le M\le I$ on the witness register. Its acceptance probability is $\mathrm{Tr}(M\rho )$, and the largest possible acceptance is $\Vert M\Vert$. Spectral bounds on $M$ make the soundness quantifier over all witnesses, including entangled repeated witnesses, explicit.