ECCC-Report TR11-110https://eccc.weizmann.ac.il/report/2011/110Comments and Revisions published for TR11-110en-usThu, 31 Jan 2013 05:37:22 +0200
Revision 1
| Improved Soundness for QMA with Multiple Provers |
Alessandro Chiesa,
Michael Forbes
https://eccc.weizmann.ac.il/report/2011/110#revision1We 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.
Thu, 31 Jan 2013 05:37:22 +0200https://eccc.weizmann.ac.il/report/2011/110#revision1
Paper TR11-110
| Improved Soundness for QMA with Multiple Provers |
Alessandro Chiesa,
Michael Forbes
https://eccc.weizmann.ac.il/report/2011/110We 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.Wed, 10 Aug 2011 07:14:37 +0300https://eccc.weizmann.ac.il/report/2011/110