{
  "annotation_id": "589e0ea4-aa3f-4796-aa77-44c5c030fc5e",
  "date_created": "2026-03-02T18:02:27.561000Z",
  "date_modified": "2026-03-02T18:02:27.561000Z",
  "file_hash": "335241d0f5739dacc6484962a647cb1f8e704938a6b8d47b6f9cf3d92d9a3e0d",
  "private": false,
  "record": {
    "abstract": "Despite the apparent similarity between shared randomness and shared\nentanglement in the context of Communication Complexity, our understanding of\nthe latter is not as good as of the former. In particular, there is no known\n\"entanglement analogue\" for the famous theorem by Newman, saying that the\nnumber of shared random bits required for solving any communication problem can\nbe at most logarithmic in the input length (i.e., using more than O(log n)\nshared random bits would not reduce the complexity of an optimal solution).\n  In this paper we prove that the same is not true for entanglement. We\nestablish a wide range of tight (up to a polylogarithmic factor) entanglement\nvs. communication tradeoffs for relational problems. The low end is: for any\nt\u003e2, reducing shared entanglement from log^t(n) to o(log^{t-2}(n)) qubits can\nincrease the communication required for solving a problem almost exponentially,\nfrom O(log^t(n)) to \\Omega(\\sqrt n). The high end is: for any \\eps\u003e0, reducing\nshared entanglement from n^{1-\\eps}log(n) to o(n^{1-\\eps}/log(n)) can increase\nthe required communication from O(n^{1-\\eps}log(n)) to\n\\Omega(n^{1-\\eps/2}/log(n)). The upper bounds are demonstrated via protocols\nwhich are exact and work in the \\e{simultaneous message passing model}, while\nthe lower bounds hold for \\e{bounded-error protocols}, even in the more\npowerful \\e{model of 1-way communication}. Our protocols use shared EPR pairs\nwhile the lower bounds apply to any sort of prior entanglement.\n  We base the lower bounds on a strong direct product theorem for communication\ncomplexity of a certain class of relational problems. We believe that the\ntheorem might have applications outside the scope of this work.",
    "arxiv_id": "quant-ph/0604052",
    "authors": [
      "Dmytro Gavinsky"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "On the Role of Shared Entanglement",
    "url": "https://arxiv.org/abs/quant-ph/0604052"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "27953453-6d89-4506-81de-4037b50893ec",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}