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

Simple item page
dc.creatorKobayashi, Hirotada
dc.creatorMatsumoto, Keiji
dc.creatorYamakami, Tomoyuki
dc.date2003-06-06
dc.date2008-05-12
dc.date.accessioned2026-07-07T09:38:06Z
dc.date.available2026-07-07T09:38:06Z
dc.descriptionThis 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., usual Merlin-Arthur proof systems), it is unclear whether or not quantum multi-proof systems collapse to quantum single-proof systems (i.e., usual quantum Merlin-Arthur 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, in the case of perfect soundness, using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems.
dc.descriptionLaTeX2e, 18 pages. The main statement (the condition under which QMA(k) = QMA(2)) is improved. The same improvement is done independently by Aaronson et al. (arXiv:0804.0802). The result of oracle separation is excluded because it follows easily from the result by Raz and Shpilka (CCC 2004)
dc.identifierhttps://arxiv.org/abs/quant-ph/0306051
dc.identifierhttp://arxiv.org/abs/quant-ph/0306051
dc.identifierConference version in Algorithms and Computation, 14th International Symposium, ISAAC 2003, volume 2906 of Lecture Notes in Computer Science, pages 189--198, 2003
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/160686
dc.subjectQuantum Physics
dc.titleQuantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
dc.typetext

Files

Collections

arXiv