dorsal/arxiv
View SchemaQuantum Weakly Nondeterministic Communication Complexity
| Authors | Francois Le Gall |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511025 |
| URL | https://arxiv.org/abs/quant-ph/0511025 |
| DOI | 10.1016/j.tcs.2012.12.015 |
| Journal | Theoretical Computer Science, Vol. 486, pp. 43-49, 2013 |
Abstract
We study the weakest model of quantum nondeterminism in which a classical proof has to be checked with probability one by a quantum protocol. We show the first separation between classical nondeterministic communication complexity and this model of quantum nondeterministic communication complexity for a total function. This separation is quadratic.
{
"annotation_id": "50feea1b-1684-43cc-b52a-ef3e78a4700c",
"date_created": "2026-03-02T18:02:20.537000Z",
"date_modified": "2026-03-02T18:02:20.537000Z",
"file_hash": "a16ec1098ed5ccb8d94345de3adc0f11c8faafd89d684d2521714a9d8aa590e9",
"private": false,
"record": {
"abstract": "We study the weakest model of quantum nondeterminism in which a classical\nproof has to be checked with probability one by a quantum protocol. We show the\nfirst separation between classical nondeterministic communication complexity\nand this model of quantum nondeterministic communication complexity for a total\nfunction. This separation is quadratic.",
"arxiv_id": "quant-ph/0511025",
"authors": [
"Francois Le Gall"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1016/j.tcs.2012.12.015",
"journal_ref": "Theoretical Computer Science, Vol. 486, pp. 43-49, 2013",
"title": "Quantum Weakly Nondeterministic Communication Complexity",
"url": "https://arxiv.org/abs/quant-ph/0511025"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e60dfc12-f9d1-45ae-a9e6-b73d649059c2",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}