CJTCS Volume 2013 Article 1

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

Alessandro Chiesa
alexh AT mit.edu
MIT, Cambridge, MA

and

Michael A. Forbes
mforbes AT mit.edu
MIT, Cambridge MA

January 13, 2013

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.
- The article: PDF (317 KB)
- Source material: ZIP (126 KB)
- BibTeX entry for this article (290 bytes)
Submitted August 9, 2011, revised November 6, 2012, and in final form January 9, 2013, published January 12, 2013.