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 proofs unentangled with each other for his verification. Although classical multi-proof are obviously equivalent to single-proof systems, it is unclear whether collapse systems. presents a necessary and sufficient condition under the number of reducible two. It also proved that using does not increase power Merlin-Arthur case perfect soundness, there relativized world co-NP (actually co-UP) have even proofs.