---
res:
bibo_abstract:
- 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, is exactly MQA (also known as QCMA),
the class of problems which can be efficiently verified via a classical proof
and a quantum verifier. 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, pp. 633--642 (2010)] that shows a perfect parallel repetition
theorem for SepQMA(m) for any m.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sevag
foaf_name: Gharibian, Sevag
foaf_surname: Gharibian
foaf_workInfoHomepage: http://www.librecat.org/personId=71541
orcid: 0000-0002-9992-3379
- foaf_Person:
foaf_givenName: Jamie
foaf_name: Sikora, Jamie
foaf_surname: Sikora
- foaf_Person:
foaf_givenName: Sarvagya
foaf_name: Upadhyay, Sarvagya
foaf_surname: Upadhyay
bibo_issue: 1-2
bibo_volume: 13
dct_date: 2013^xs_gYear
dct_language: eng
dct_title: QMA variants with polynomially many provers@
...