Computer Science – Computational Complexity
Scientific paper
2005-06-15
Computational Complexity, 14(2): 122 - 152, 2005
Computer Science
Computational Complexity
22 pages
Scientific paper
This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA is contained in PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur-Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur-Merlin games.
Marriott Chris
Watrous John
No associations
LandOfFree
Quantum Arthur-Merlin Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Arthur-Merlin Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Arthur-Merlin Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-4871