Chicago Journal of Theoretical Computer Science

Volume 2012

Article 9

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

On Quantum Interactive Proofs with Short Messages

Attila Pereszlényi
Centre for Quantum Technologies
National University of Singapore

December 1st, 2012


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.

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

DOI: 10.4086/cjtcs.2012.009

[] Volume 2012, Article 8 [] Volume 2012, Article 10
[back] Volume 2012 [back] Published articles
[CJCTS home]