Improved Soundness for QMA with Multiple Provers

Authors: Alessandro Chiesa and Michael Forbes.

Bibliographic information: In the Chicago Journal of Theoretical Computer Science, volume 2013, number 1, pages 1-23. (BibTeX)


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}). Our improvement is achieved \emph{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 \emph{needed} in order to have any soundness gap, to a protocol with a \emph{smooth trade-off} between the number of provers k and a soundness gap \Omega(k^{2}N^{-1}), 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 \emph{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.

Find the paper on [arXiv] and on [CJTCS].

Alessandro Chiesa
Last modified: Tue, 15 Jan 2013 11:49:56 -0500
Valid HTML 4.01 Strict