Physics – Quantum Physics
Scientific paper
2011-08-02
Physics
Quantum Physics
22 pages, no figures
Scientific paper
We study three variants of multi-prover quantum Merlin-Arthur proof systems. We first show that the class of problems that can be efficiently verified using polynomially many quantum proofs, each of logarithmic-size (denoted QMA_log(poly)), is exactly MQA, the class of problems which can be efficiently verified via a classical proof and a quantum verifier. Assuming BQP \neq MQA, this achieves the separation QMA_log(1) \neq QMA_log(poly). We then study the class BellQMA(poly), characterized by a verifier who first applies unentangled, nonadaptive measurements to each of the polynomially many proofs, followed by an arbitrary but efficient quantum verification circuit on the resulting measurement outcomes. We show that if the number of outcomes per nonadaptive measurement is a polynomially-bounded function, then the expressive power of the proof system is exactly QMA. Finally, we study a class equivalent to QMA(m), denoted SepQMA(m), where the verifier's measurement operator corresponding to outcome accept is a fully separable operator across the m quantum proofs. Using cone programming duality, we give an alternate proof of a result of Harrow and Montanaro [FOCS, p. 633--642 (2010)] that shows a perfect parallel repetition theorem for SepQMA(m) for any m.
Gharibian Sevag
Sikora Jamie
Upadhyay Sarvagya
No associations
LandOfFree
QMA variants with polynomially many 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 QMA variants with polynomially many provers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QMA variants with polynomially many provers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-510401