{
  "annotation_id": "82dea80c-4a4c-48fd-bcaf-91d5531d3414",
  "date_created": "2026-03-02T18:02:13.278000Z",
  "date_modified": "2026-03-02T18:02:13.278000Z",
  "file_hash": "fbe9fd5e5b67f06da3a117f3d82f108c92d60669d1937266f67c2b21bf36043b",
  "private": false,
  "record": {
    "abstract": "We study the simultaneous message passing model of communication complexity.\nBuilding on the quantum fingerprinting protocol of Buhrman et al., Yao recently\nshowed that a large class of efficient classical public-coin protocols can be\nturned into efficient quantum protocols without public coin. This raises the\nquestion whether this can be done always, i.e. whether quantum communication\ncan always replace a public coin in the SMP model. We answer this question in\nthe negative, exhibiting a communication problem where classical communication\nwith public coin is exponentially more efficient than quantum communication.\nTogether with a separation in the other direction due to Bar-Yossef et al.,\nthis shows that the quantum SMP model is incomparable with the classical\npublic-coin SMP model.\n  In addition we give a characterization of the power of quantum fingerprinting\nby means of a connection to geometrical tools from machine learning, a\nquadratic improvement of Yao\u0027s simulation, and a nearly tight analysis of the\nHamming distance problem from Yao\u0027s paper.",
    "arxiv_id": "quant-ph/0411051",
    "authors": [
      "Dmytro Gavinsky",
      "Julia Kempe",
      "Ronald de Wolf"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Quantum Communication Cannot Simulate a Public Coin",
    "url": "https://arxiv.org/abs/quant-ph/0411051"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e73837d8-4707-4e0f-9a5f-e55c374f6d78",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}