Published by the Department of Computer Science, The University of Chicago.
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.