Class Description

QMAM: Quantum Merlin-Arthur-Merlin Public-Coin Interactive Proofs

The class of decision problems for which a "yes" answer can be verified by a public-coin quantum MAM protocol, as follows. Merlin sends a polynomial-size quantum state to Arthur. Arthur then flips some classical coins (in fact, he only has to flip one without loss of generality) and sends the outcome to Merlin. At this stage Arthur is not yet allowed to perform any quantum operations. Merlin then sends Arthur another quantum state. Finally, Arthur performs a BQP operation on both of the states simultaneously, and either accepts or rejects. The completeness and soundness requirements are the same as for AM. Also, Merlin's messages might be entangled.

Defined by Marriott and Watrous [MW05], who also showed that QMAM = QIP(3) = QIP.

Hence QMAM equals PSPACE.

Linked From

No class.