{
  "annotation_id": "d623dbb8-3450-460b-83ba-c7471abcb489",
  "date_created": "2026-03-02T18:02:33.452000Z",
  "date_modified": "2026-03-02T18:02:33.452000Z",
  "file_hash": "ead65ac953ad9837b0232910b480aed578185f5ec8867d617bc9b79e1073a59d",
  "private": false,
  "record": {
    "abstract": "We give an exponential separation between one-way quantum and classical\ncommunication protocols for a partial Boolean function (a variant of the\nBoolean Hidden Matching Problem of Bar-Yossef et al.) Earlier such an\nexponential separation was known only for a relational problem. The\ncommunication problem corresponds to a \\emph{strong extractor} that fails\nagainst a small amount of \\emph{quantum} information about its random source.\nOur proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial.\n  We also give a number of applications of this separation. In particular, we\nshow that there are privacy amplification schemes that are secure against\nclassical adversaries but not against quantum adversaries; and we give the\nfirst example of a key-expansion scheme in the model of bounded-storage\ncryptography that is secure against classical memory-bounded adversaries but\nnot against quantum ones.",
    "arxiv_id": "quant-ph/0611209",
    "authors": [
      "Dmytro Gavinsky",
      "Julia Kempe",
      "Iordanis Kerenidis",
      "Ran Raz",
      "Ronald de Wolf"
    ],
    "categories": [
      "quant-ph"
    ],
    "journal_ref": "Proc. 39th STOC, p. 516-525 (2007)",
    "title": "Exponential separations for one-way quantum communication complexity,   with applications to cryptography",
    "url": "https://arxiv.org/abs/quant-ph/0611209"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "6cd0de90-4678-4ef5-8bcb-0c46cc06554a",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}