### Volume 2013

#### Improved Soundness for QMA with Multiple Provers

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

and

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

January 13, 2013

#### Abstract

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)