We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap Omega(1/N^2). Our improvement is achieved without the use of an instance with a constant soundness gap (i.e., without using a PCP).

2) We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV '10], thereby improving their result from a monolithic protocol where Theta(sqrt(N)) provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers k and a soundness gap Omega(k^2/N), as long as k>=Omega(log N). (And, when k=Theta(sqrt(N)), we recover the original parameters of Chen and Drucker.)

3) We make progress towards an open question of [Aaronson et al., ToC '09] about what kinds of NP-complete problems are amenable to sublinear multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature - namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time.

revisions for clarity; published as Chicago Journal of Theoretical Computer Science, Vol 2013, No 1

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap \Omega(N^{-2}), which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe surprisingly, our improvement is achieved without the use of an instance with a constant soundness gap (i.e., without using a PCP); this is unlike the previously best-known soundness gap of \Omega(N^{-3- \epsilon}) given by [Beigi, QIC '10], which was achieved using a (balanced) 2-out-of-4 instance with constant soundness gap.

2) We give a tight soundness analysis of the protocol of [Chen and Drucker, ArXiV '10], thereby improving their result from a monolithic protocol where \Theta(\sqrt{N}) provers are needed in order to have any soundness gap, to a protocol with a smooth trade-off between the number of provers \kappa and a soundness gap \Omega(\kappa^{2}N^{-1}), as long as \kappa \in \Omega(\log N). (And, when \kappa \in \Theta(\sqrt{N}), we recover the original parameters of Chen and Drucker.) Further, we explain why even our tight analysis cannot give any soundness gap for the \kappa \in O(1) regime, implying that new protocols are needed for any sublinear constant-prover LOCC QMA protocol with an inverse-polynomial soundness gap.

3) We make partial progress towards an open question of [Aaronson et al., ToC '09] about what kinds of NP-complete problems are amenable to sublinear multiple-prover QMA protocols, by observing that a large class of such examples can easily be derived from results already in the PCP literature --- namely, at least the languages recognized by a non-deterministic RAMs in quasilinear time. We also take the opportunity to give generic lemmas that allow for such results to be stated in a more general (and unified) way.