Theory of Computing
-------------------
Title : Quantum Interactive Proofs with Short Messages
Authors : Salman Beigi, Peter Shor, and John Watrous
Volume : 7
Number : 7
Pages : 101-117
URL : https://theoryofcomputing.org/articles/v007a007
Abstract
--------
This paper considers three variants of quantum interactive
proof systems in which short (meaning logarithmic-length) messages
are exchanged between the prover and verifier. The first variant
is one in which the verifier sends a short message to the prover,
and the prover responds with an ordinary, or polynomial-length,
message; the second variant is one in which any number of messages
can be exchanged, but where the combined length of all the messages
is logarithmic; and the third variant is one in which the verifier
sends polynomially many random bits to the prover, who responds
with a short quantum message.
We prove that in all of these cases the short messages can be
eliminated without changing the power of the model, so the first
variant has the expressive power of QMA and the second and third
variants have the expressive power of BQP. These facts are proved
through the use of quantum state tomography, along with the finite
quantum de Finetti theorem for the first variant.