{
  "annotation_id": "4ebc75c3-9f5b-4233-94c0-8e6ffbd6b9c0",
  "date_created": "2026-03-02T18:02:29.885000Z",
  "date_modified": "2026-03-02T18:02:29.885000Z",
  "file_hash": "89f5507d441a7d7df72a8c19fe340a91c6e2a8480c11db1012db7de6d66f8ea1",
  "private": false,
  "record": {
    "abstract": "We give a tight lower bound of Omega(\\sqrt{n}) for the randomized one-way\ncommunication complexity of the Boolean Hidden Matching Problem [BJK04]. Since\nthere is a quantum one-way communication complexity protocol of O(\\log n)\nqubits for this problem, we obtain an exponential separation of quantum and\nclassical one-way communication complexity for partial functions. A similar\nresult was independently obtained by Gavinsky, Kempe, de Wolf [GKdW06]. Our\nlower bound is obtained by Fourier analysis, using the Fourier coefficients\ninequality of Kahn Kalai and Linial [KKL88].",
    "arxiv_id": "quant-ph/0607173",
    "authors": [
      "Iordanis Kerenidis",
      "Ran Raz"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "The one-way communication complexity of the Boolean Hidden Matching   Problem",
    "url": "https://arxiv.org/abs/quant-ph/0607173"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "932587f3-2298-474c-9711-61ef61f2aa8e",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}