| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? | Hirotada Kobayashi
; Keiji Matsumoto
; Tomoyuki Yamakami
; | Date: |
6 Jun 2003 | Subject: | quant-ph | Abstract: | Quantum Merlin-Arthur proof systems are a weak form of quantum interactive proof systems, where mighty Merlin as a prover presents a proof in a pure quantum state and Arthur as a verifier performs polynomial-time quantum computation to verify its correctness with high success probability. For a more general treatment, this paper considers quantum ``multiple-Merlin’’-Arthur proof systems in which Arthur uses multiple quantum proofs unentangled each other for his verification. Although classical multi-proof systems are easily shown to be essentially equivalent to classical single-proof systems, it is unclear whether quantum multi-proof systems collapse to quantum single-proof systems. This paper investigates the possibility that quantum multi-proof systems collapse to quantum single-proof systems, and shows that (i) a necessary and sufficient condition under which the number of quantum proofs is reducible to two and (ii) using multiple quantum proofs does not increase the power of quantum Merlin-Arthur proof systems in the case of perfect soundness. Our proof for the latter result also gives a new characterization of the class NQP, which bridges two existing concepts of ``quantum nondeterminism’’. It is also shown that (iii) 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. | Source: | arXiv, quant-ph/0306051 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |