Dishonest Proofs in QMA

Question

My question concerns the acceptance probability of dishonest proofs in the YES case of a QMA verification protocol.

According to the canonical definition of QMA, the completeness condition requires the existence of at least one quantum proof (witness state) that the verifier accepts with probability at least $2/3$. In proofs of containment in QMA, the focus is typically on constructing such a "good" proof and verifying that it meets this threshold. This makes sense, as the definition only requires the existence of one good proof, not a guarantee about the behaviour of other proofs.

However, what happens if Merlin sends a dishonest proof -- a proof that is not the intended witness state? The QMA definition does not impose any restrictions on the acceptance probability of such dishonest proofs in the YES case. This stands in contrast to stricter classes like GQMA [1], PGQMA [2] and UQMA [3], which explicitly define criteria for both honest and dishonest proofs in the completeness and soundness regimes. These classes appear more robust against dishonest proofs, as they impose additional structure on the verification process.

This raises several questions:

1. Is it the responsibility of the verifier to ensure that dishonest proofs are rejected with high probability, even in the YES case?
2. Does the soundness condition in QMA, which requires that all proofs are rejected with probability at most $1/3$ in the NO case, also constrain the acceptance probability of dishonest proofs in the YES case? For instance, if Merlin sends a dishonest proof that is very close to an honest proof, could it be accepted with probability significantly higher than $1/3$ ? (comments in [3] seems to suggest the probability could be high)

A poorly designed verification protocol might satisfy QMA's completeness and soundness conditions while still allowing dishonest proofs to slip through with non-negligible probability. On the other hand, the local Hamiltonian problem's promise gap might implicitly constrain the acceptance probability of dishonest proofs (e.g., by linking acceptance rates to energy expectation values). However, this is not explicitly demanded by the QMA definition.

In summary, while QMA does not impose explicit thresholds on the acceptance probability of dishonest proofs in the YES case, stricter classes like GQMA, PGQMA, UQMA suggest that such considerations are important in practice. How should we interpret the behaviour of dishonest proofs in QMA, and what role does the verifier play in ensuring robustness against them? Is it best to understand the behaviour simply as GQMA$(c,s,0,0)$ = QMA(c,s) [1]?

---

Edit 1:

A succinct question for clarity: What constraints, if any, does QMA place on the acceptance probability of dishonest proofs in the YES case?

Hopefully, this is clearer and more to the point.

It seems like the answer is ''no constraints'', but I am not yet fully understanding of this conclusion.

---

Edit 2:

The consensus appears to be that by definition QMA does not place a constraint on the acceptance bound for dishonest proofs, and instead, such a bound can be found via the authentication and verification protocol constructed by Arthur. This leaves a degree of freedom for Arthur in that, it is up to them to figure out if they want to distinguish honest from dishonest proof with high probability. Moreover, QMA containment (for the YES case) doesn't require them to distinguish with confidence. However, the soundness element may impact this.

Answer 1

[0001] I'm not sure I understand the question the way it's phrased, but based on the comments I think some things can be clarified by considering the differences in the different gaps.

[0002] In general the spectral gap is different from the promise gap, which is different still from the gap in the soundness/completeness probabilities between acceptance and rejection. See here for example.

[0003] Let $b-a$ be the promise gap; let $\lambda_2-\lambda_1$ be the spectral gap. Further let $\rm{Pr}_A-\rm{Pr}_B$ be the difference between accepting and rejecting probabilities.

[0004] In the original QMA protocol, the second smallest eigenvalue $\lambda_2$ could be between the smallest eigenvalue $\lambda_1$ and the promise gap $b-a$. Arthur only verifies that the smallest eigenvalue $\lambda_1$ is less than $a$ and not greater than $b$, under the promise that it's not greater than $a$ and less than $b$.

[0005] That is, $\lambda_2$ can be greater than $a$ and still less than $b$. We could have $\lambda_2=a+\epsilon$. Indeed the density of states in the gap from $a$ to $b$ could be infinite. Also, nothing precludes degeneracy in the ground state - as long as Merlin sends at least one eigenstate $|\psi\rangle$ with eigenvalue $\le a$, Arthur should accept.

[0006] The gap between accepting and rejecting probabilities just needs to be a positive constant. We could have $\rm{Pr}_A$ be $51\%$ or even $50.000001\%$, and $\rm{Pr}_B$ be $49\%$ or even $50\%$; Arthur can always amplify this difference using Marriott-Watrous gap amplification. The choice of $2/3$ and $1/3$ is just conventional.

---

[0007] As to the motivations behind the other probabilities, we require $\rm{Pr}_A-\rm{Pr}_B$ to be independent of $n$. These I think are what the post refers to as $c$ and $s$.

[0008] The above discussions were focusing on the $k$-local Hamiltonian problem, which is well-motivated physically. But Watrous also concurrently proved another famous and less physical example of a problem in QMA - that of Group Non-Membership.

[0009] In particular, given a group $G$ and a set of generators of $\{g_1,g_2,\cdots,g_k\}\in G$, Merlin can prove to Arthur that $h\not\in H=\langle g_1,g_2,\cdots,g_k\rangle$ by providing a state $|\psi\rangle$ to Arthur purported to be the uniform distribution over all elements of $H$.

[0010] Arthur can do a simple first controlled test on $|\psi\rangle$ to prove that $h\not\in G$, but he also must every now and then decide to perform a second projective test and confirm that $|\psi\rangle$ really is (close to) the uniform superposition over all elements of $H$. So I guess in this case we can say that Arthur is responsible to confirm that $|\psi\rangle$ is really an honest state.

[0011] If $|\psi\rangle$ is only close to the uniform superposition over all elements of $H$, then Watrous's paper has a wonderful line about this second test:

Under the assumption that [the second test succeeds], however, the state [of $|\psi\rangle$] will in fact be changed (by quantum magic!) to one that is invariant under right multiplication by elements in $H$.

[0012] I guess to answer the main question: any foolish Merlin can give any state to Arthur; it's Arthur's burden to make sure that the state is what it's purported to be.

[0013] In the above example, Merlin could have given a monkey state $|\psi'\rangle$ to Arthur, such as a maximally mixed state, even if $h$ is not a member of $H$. In that situation, Arthur would run the second test and conclude that Merlin had given him garbage. Arthur would then know nothing about the true, platonic world of whether $h\not\in H$.