Chicago Journal of Theoretical Computer Science

Volume 2009

Article 3

Published by Dept. CS U. Chicago. Copyright 2009 CJTCS and the author.

Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?

Hirotada Kobayashi
Principles of Informatics Research Division
National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430
Keiji Matsumoto
Quantum Computation and Information Project
Solution Oriented Research for Science and Technology
Japan Science and Technology Agency
5-28-3 Hongo, Bunkyo-ku, Tokyo 113-003
Tomoyuki Yamakami
Department of Information Science
University of Fukui
3-9-1 Bunkyo, Fukui City, Fukui 910-8507

July 17, 2009

This paper introduces quantum "multiple--Merlin"--Arthur proof systems in which Arthur receives multiple quantum proofs that are unentangled with each other. Although classical multi-proof systems are obviously equivalent to classical single-proof systems (i.e., standard Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., standard quantum Merlin-Arthur proof systems). This paper presents a way of reducing the number of proofs to two while keeping the two-sided bounded-error property, which gives a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.

DOI: 10.4086/cjtcs.2009.003
[] Volume 2009, Article 2 [] Volume 2010, Article 1
[back] Volume 2009 [back] Published articles
[CJCTS home]