article
QMA variants with polynomially many provers
published
Sevag
Gharibian
author 715410000-0002-9992-3379
Jamie
Sikora
author
Sarvagya
Upadhyay
author
596
department
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.
2013
eng
Quantum Information & Computation
1108.0617
131-2135-157
yes
S. Gharibian, J. Sikora, S. Upadhyay, Quantum Information & Computation 13 (2013) 135–157.
S. Gharibian, J. Sikora, and S. Upadhyay, “QMA variants with polynomially many provers,” <i>Quantum Information & Computation</i>, vol. 13, no. 1–2, pp. 135–157, 2013.
Gharibian, Sevag, Jamie Sikora, and Sarvagya Upadhyay. “QMA Variants with Polynomially Many Provers.” <i>Quantum Information & Computation</i> 13, no. 1–2 (2013): 135–57.
@article{Gharibian_Sikora_Upadhyay_2013, title={QMA variants with polynomially many provers}, volume={13}, number={1–2}, journal={Quantum Information & Computation}, author={Gharibian, Sevag and Sikora, Jamie and Upadhyay, Sarvagya}, year={2013}, pages={135–157} }
Gharibian S, Sikora J, Upadhyay S. QMA variants with polynomially many provers. <i>Quantum Information & Computation</i>. 2013;13(1-2):135-157.
Gharibian, Sevag, et al. “QMA Variants with Polynomially Many Provers.” <i>Quantum Information & Computation</i>, vol. 13, no. 1–2, 2013, pp. 135–57.
Gharibian, S., Sikora, J., & Upadhyay, S. (2013). QMA variants with polynomially many provers. <i>Quantum Information & Computation</i>, <i>13</i>(1–2), 135–157.
81732019-03-01T12:00:39Z2019-03-06T22:00:06Z