文章基本信息

标题：Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
本地全文：下载
作者：Hirotada Kobayashi ; Keiji Matsumoto ; Tomoyuki Yamakami. 等
期刊名称：Chicago Journal of Theoretical Computer Science
印刷版ISSN：1073-0486
出版年度：2009
卷号：2009
出版社：MIT Press ; University of Chicago, Department of Computer Science
摘要：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.