Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
复制标题
DOI：
10.1007/978-3-540-24587-2_21
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
Hirotada Kobayashi;Keiji Matsumoto;T. Yamakami
中科院分区：
文献类型：
--
作者：
Hirotada Kobayashi;Keiji Matsumoto;T. Yamakami
本文介绍了量子“多梅林”-亚瑟证明系统，其中亚瑟使用多个彼此不纠缠的量子证明进行验证。尽管经典多重证明系统显然等同于经典单证明系统，但尚不清楚量子多重证明系统是否会崩溃为量子单证明系统。本文提出了一个充分必要条件，在该条件下量子证明的数量可以减少到两个。还证明了在完美健全的情况下，使用多重量子证明并不会增加量子Merlin-Arthur证明系统的威力，并且存在一个相对化的世界，其中co-NP（实际上是co-UP）即使有多重量子证明也没有量子Merlin-Arthur证明系统。
This paper introduces quantum “multiple-Merlin”-Arthur proof systems in which Arthur uses multiple quantum proofs unentangled with each other for his verification. Although classical multi-proof systems are obviously equivalent to classical single-proof systems, it is unclear whether quantum multi-proof systems collapse to quantum single-proof systems. This paper presents a necessary and sufficient condition under which the number of quantum proofs is reducible to two. It is also proved that using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems in the case of perfect soundness, and that there is a relativized world in which co-NP (actually co-UP) does not have quantum Merlin-Arthur proof systems even with multiple quantum proofs.