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

摘要

This paper introduces quantum "multiple-Merlin"-Arthur proof systems in which Arthur uses multiple quantum proofs unentan-gled 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.