Published by the Department of Computer Science, The University of Chicago.

MIT, Cambridge, MA

and

Michael A. Forbes

`mforbes AT mit.edu`

MIT, Cambridge MA

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

- We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM
2009], yielding a soundness gap
$\Omega(N^{-2})$. Our improvement is achieved
*without*the use of an instance w ith a constant soundness gap (i.e., without using a ``PCP''). - We give a tight soundness analysis of the protocol of
[Chen and Drucker, ArXiV 2010], 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 \Omega(\log N)$, we recover the original parameters of Chen and Drucker.) - We make progress towards an open question of [Aaronson et al., ToC 2009]
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.

Submitted August 9, 2011, revised November 6, 2012, and in final form January 9, 2013, published January 12, 2013.

© 2013 Alessandro Chiesa and Michael A. Forbes

Licensed under a Creative Commons Attribution License

Licensed under a Creative Commons Attribution License

Volume 2012, Article 10 Article 2

Volume 2013 Published articles