dorsal/arxiv
View SchemaOn parallel composition of zero-knowledge proofs with black-box quantum simulators
| Authors | Rahul Jain, Alexandra Kolla, Gatis Midrijanis, Ben W. Reichardt |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0607211 |
| URL | https://arxiv.org/abs/quant-ph/0607211 |
| Journal | Quant. Inf. Comp. 9:513-532, 2009 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator S, then L in BQP. Our result also applies to any language having a three-round quantum interactive proof (QIP), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when L notin BQP would imply an impossibly-good quantum search algorithm.
{
"annotation_id": "9332bfcc-62c9-4ee3-9d7f-e654871c8024",
"date_created": "2026-03-02T18:02:29.887000Z",
"date_modified": "2026-03-02T18:02:29.887000Z",
"file_hash": "6ae98e9b8c057462232525fcc81746cd6f9721819d34570afbbe1f16a8415360",
"private": false,
"record": {
"abstract": "Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM)\nprotocol with negligible soundness error and all but possibly the last message\nbeing classical. We prove that if this protocol is zero knowledge with a\nblack-box, quantum simulator S, then L in BQP. Our result also applies to any\nlanguage having a three-round quantum interactive proof (QIP), with all but\npossibly the last message being classical, with negligible soundness error and\na black-box quantum simulator.\n These results in particular make it unlikely that certain protocols can be\ncomposed in parallel in order to reduce soundness error, while maintaining zero\nknowledge with a black-box quantum simulator. They generalize analogous\nclassical results of Goldreich and Krawczyk (1990).\n Our proof goes via a reduction to quantum black-box search. We show that the\nexistence of a black-box quantum simulator for such protocols when L notin BQP\nwould imply an impossibly-good quantum search algorithm.",
"arxiv_id": "quant-ph/0607211",
"authors": [
"Rahul Jain",
"Alexandra Kolla",
"Gatis Midrijanis",
"Ben W. Reichardt"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quant. Inf. Comp. 9:513-532, 2009",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "On parallel composition of zero-knowledge proofs with black-box quantum simulators",
"url": "https://arxiv.org/abs/quant-ph/0607211"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "29dca231-29fc-4751-980e-193bf92e4bec",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}