= Solution
Interpret the high-success formulation as completeness at least $1-\delta(n)$ and soundness at most $\delta(n)$, where $\delta(n)\leq1/p(n)$ for a growing polynomial $p$. This is the standard error-reduction claim. Literally placing $O$ around a success probability approaching one supplies no useful lower bound; it is the failure probability that must be inverse-polynomially small.
Let $M_x$ be the <quantum verifier acceptance operator> acting on one witness register:
$$
M_x=(I\otimes\langle0|)V_x^\dagger
(I\otimes|1\rangle\langle1|_{\rm out})V_x(I\otimes|0\rangle),
\qquad 0\leq M_x\leq I.
$$
Acceptance on $\rho$ is $\operatorname{Tr}(M_x\rho)$. On a NO instance, $\|M_x\|\leq1/3$; on a YES instance, an honest witness has acceptance at least $2/3$.
Ask for $r$ witness registers, with $r$ odd, run $V_x$ independently on each register with fresh ancillas, and accept a strict majority. The <QMA parallel repetition with entangled witnesses> acceptance operator is
$$
M_x^{(r)}=
\sum_{\substack{z\in\{0,1\}^r\\ |z|>r/2}}
\bigotimes_{j=1}^r M_x^{z_j}(I-M_x)^{1-z_j}.
$$
Diagonalize $M_x$. In the tensor-product eigenbasis, an <eigenvalue> of $M_x^{(r)}$ is the majority probability for independent <Bernoulli random variables> with parameters equal to the selected eigenvalues of $M_x$. On a NO instance every parameter is at most $1/3$. Coupling these variables using independent uniform random numbers shows that their upper majority tail is bounded by the tail with every parameter $1/3$. This bounds the operator norm and therefore covers every supplied witness, including a witness entangled across the registers. No independence assumption about a dishonest witness is being made.
For a valid <Chernoff bound>, if $S$ is a sum of $r$ independent Bernoulli variables of parameter at most $1/3$, <Markov's inequality> applied to $2^S$ yields
$$
\Pr(S\geq r/2)
\leq2^{-r/2}\left(\frac23+\frac13\,2\right)^r
=\left(\frac{2\sqrt2}{3}\right)^r
=e^{-cr},\qquad c=\frac12\ln\frac98>0.
$$
An honest product witness on a YES instance gives independent trials with rejection probability at most $1/3$, so its failure probability has the same bound. The printed concentration bound is not valid as stated: for five trials at parameter $1/3$, the upper-majority probability is $17/81>e^{-5/3}$. The valid bound above suffices for a rigorous proof.
Choose the next odd integer above $c^{-1}\ln p(n)$. Then
$$
\boxed{\text{completeness}\geq1-\frac1{p(n)},\qquad
\text{soundness}\leq\frac1{p(n)}.}
$$
The witness length and circuit size increase by only $O(\log p(n))$; the majority calculation has polynomial overhead. Conversely, inverse-polynomial failure probability is at most $1/3$ for all sufficiently large input lengths. Finitely many smaller lengths can be handled by hard-wired verifiers, giving the usual constants. Hence \b[the two definitions give the same class QMA]. The same <QMA error reduction> argument also yields exponentially small failure with polynomially many copies.
Back to article page
