Physics – Quantum Physics
Scientific paper
2011-08-10
Physics
Quantum Physics
25 pages; comments welcome
Scientific paper
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(1/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(1/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 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.) Further, we explain why even our tight analysis cannot give any soundness gap for the k=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.
Chiesa Alessandro
Forbes Michael
No associations
LandOfFree
Improved Soundness for QMA with Multiple Provers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Improved Soundness for QMA with Multiple Provers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Soundness for QMA with Multiple Provers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-664833