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

Abstract

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.

• Preformatted versions of the article
  • PDF (249.903 bytes)

DOI: 10.4086/cjtcs.2009.003

---

Volume 2009, Article 2 Volume 2010, Article 1
Volume 2009 Published articles