dorsal/arxiv
View SchemaQuantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
| Authors | Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0306051 |
| URL | https://arxiv.org/abs/quant-ph/0306051 |
| Journal | Conference version in Algorithms and Computation, 14th International Symposium, ISAAC 2003, volume 2906 of Lecture Notes in Computer Science, pages 189--198, 2003 |
Abstract
This 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.
{
"annotation_id": "a54dd68d-0ac5-4369-8fd5-f145b1ab8ef5",
"date_created": "2026-03-02T18:01:59.663000Z",
"date_modified": "2026-03-02T18:01:59.663000Z",
"file_hash": "db444246eb3e168f11ccdfe03509d627761e74a9b490a236328b02bd164b6d91",
"private": false,
"record": {
"abstract": "This paper introduces quantum ``multiple-Merlin\u0027\u0027-Arthur proof systems in\nwhich Arthur receives multiple quantum proofs that are unentangled with each\nother. Although classical multi-proof systems are obviously equivalent to\nclassical single-proof systems (i.e., usual Merlin-Arthur proof systems), it is\nunclear whether or not quantum multi-proof systems collapse to quantum\nsingle-proof systems (i.e., usual quantum Merlin-Arthur proof systems). This\npaper presents a necessary and sufficient condition under which the number of\nquantum proofs is reducible to two. It is also proved that, in the case of\nperfect soundness, using multiple quantum proofs does not increase the power of\nquantum Merlin-Arthur proof systems.",
"arxiv_id": "quant-ph/0306051",
"authors": [
"Hirotada Kobayashi",
"Keiji Matsumoto",
"Tomoyuki Yamakami"
],
"categories": [
"quant-ph"
],
"journal_ref": "Conference version in Algorithms and Computation, 14th\n International Symposium, ISAAC 2003, volume 2906 of Lecture Notes in Computer\n Science, pages 189--198, 2003",
"title": "Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?",
"url": "https://arxiv.org/abs/quant-ph/0306051"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "8fc6c46a-82af-4c5c-8f53-5aeb8f774a52",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}