Quantum Arthur-Merlin Games

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Chris Marriott Articles by John Watrous

19th Annual IEEE Conference on Computational Complexity (CCC'04)

Amherst, Massachusetts

June 21-June 24

ISBN: 0-7695-2120-7

	ASCII Text	x
	Chris Marriott, John Watrous, "Quantum Arthur-Merlin Games," Computational Complexity, Annual IEEE Conference on, pp. 275-285, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.

	BibTex	x
	@article{ 10.1109/CCC.2004.1313850, author = {Chris Marriott and John Watrous}, title = {Quantum Arthur-Merlin Games}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {2004}, issn = {1093-0159}, pages = {275-285}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313850}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Quantum Arthur-Merlin Games SN - 1093-0159 SP275 EP285 A1 - Chris Marriott, A1 - John Watrous, PY - 2004 KW - null VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Chris Marriott, University of Calgary

John Watrous, University of Calgary

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313850

This paper studies quantum Arthur-Merlin games, which are a restricted form of quantum interactive proof system in which the verifier?s messages are given by unbiased coin- flips. The following results are proved.

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 ⊆ PP.

In the case of three or more messages, quantum Arthur- Merlin games are equivalent in power to ordinary quantum interactive proof systems. In fact, for any language having a quantum interactive proof system there exists a three-message quantum Arthur-Merlin game in which Arthur?s only message consists of just a single coin-flip that achieves perfect completeness and soundness error exponentially close to 1/2.

Any language having a two-message quantum Arthur- Merlin game is contained in BP \cdot PP. This gives some suggestion that three messages are stronger than two in the quantum Arthur-Merlin setting.

Citation:

Chris Marriott, John Watrous, "Quantum Arthur-Merlin Games," ccc, pp.275-285, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.