Published by Dept. CS U. Chicago. Copyright 2009 CJTCS and the author.
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.