dorsal/arxiv
View SchemaA Note on Shared Randomness and Shared Entanglement in Communication
| Authors | Dmytro Gavinsky |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0505088 |
| URL | https://arxiv.org/abs/quant-ph/0505088 |
Abstract
We consider several models of 1-round classical and quantum communication, some of these models have not been defined before. We "almost separate" the models of simultaneous quantum message passing with shared entanglement and the model of simultaneous quantum message passing with shared randomness. We define a relation which can be efficiently exactly solved in the first model but cannot be solved efficiently, either exactly or in 0-error setup in the second model. In fact, our relation is exactly solvable even in a more restricted model of simultaneous classical message passing with shared entanglement. As our second contribution we strengthen a result by Yao that a "very short" protocol from the model of simultaneous classical message passing with shared randomness can be simulated in the model of simultaneous quantum message passing: for a boolean function f, QII(f) \in exp(O(RIIp(f))) log n. We show a similar result for protocols from a (stronger) model of 1-way classical message passing with shared randomness: QII(f) \in exp(O(RIp(f))) log n. We demonstrate a problem whose efficient solution in the model of simultaneous quantum message passing follows from our result but not from Yao's.
{
"annotation_id": "6776495e-0b38-456d-b26b-267604177a8d",
"date_created": "2026-03-02T18:02:16.428000Z",
"date_modified": "2026-03-02T18:02:16.428000Z",
"file_hash": "a86615480637cfec24484b4d0b430e72439f60decdd8e12b9e722a2ba5069a87",
"private": false,
"record": {
"abstract": "We consider several models of 1-round classical and quantum communication,\nsome of these models have not been defined before. We \"almost separate\" the\nmodels of simultaneous quantum message passing with shared entanglement and the\nmodel of simultaneous quantum message passing with shared randomness. We define\na relation which can be efficiently exactly solved in the first model but\ncannot be solved efficiently, either exactly or in 0-error setup in the second\nmodel. In fact, our relation is exactly solvable even in a more restricted\nmodel of simultaneous classical message passing with shared entanglement.\n As our second contribution we strengthen a result by Yao that a \"very short\"\nprotocol from the model of simultaneous classical message passing with shared\nrandomness can be simulated in the model of simultaneous quantum message\npassing: for a boolean function f, QII(f) \\in exp(O(RIIp(f))) log n.\n We show a similar result for protocols from a (stronger) model of 1-way\nclassical message passing with shared randomness: QII(f) \\in exp(O(RIp(f))) log\nn.\n We demonstrate a problem whose efficient solution in the model of\nsimultaneous quantum message passing follows from our result but not from\nYao\u0027s.",
"arxiv_id": "quant-ph/0505088",
"authors": [
"Dmytro Gavinsky"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "A Note on Shared Randomness and Shared Entanglement in Communication",
"url": "https://arxiv.org/abs/quant-ph/0505088"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "cce03828-71fd-4a8d-9c9e-a8f981724bb1",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}