Published by the Department of Computer Science, The University of Chicago.

Abstract

This paper proves one of the open problems posed by Beigi, Shor and Watrous in Theory of Computing volume 7, article 7, pp. 101-117 (2011). We consider quantum interactive proof systems where, in the beginning, the verifier and prover send messages to each other, with the combined length of all messages being at most logarithmic (in the input length); and at the end, the prover sends a polynomial-length message to the verifier. We show that this class has the same expressive power as QMA.

• The article: PDF (217 Kbytes)
• Source material: ZIP (299 Kbytes)
• BibTeX entry for this article (251 bytes)

Submitted June 4, 2012, revised October 19,2012 and November 30,2012, published December 1, 2012.

© 2012 Attila Pereszlényi
Licensed under a Creative Commons Attribution License

Volume 2012, Article 8

Volume 2012, Article 10

Volume 2012

Published articles