{
  "annotation_id": "675324c7-7eba-4365-a4c4-023166e4ebaf",
  "date_created": "2026-03-02T18:02:20.415000Z",
  "date_modified": "2026-03-02T18:02:20.415000Z",
  "file_hash": "d30730f31dc398efcc6290b1633e21740f3b64149bb1fddc6900a862e8cfac20",
  "private": false,
  "record": {
    "abstract": "Two-party one-way quantum communication has been extensively studied in the\nrecent literature. We target the size of minimal information that is necessary\nfor a feasible party to finish a given combinatorial task, such as distinction\nof instances, using one-way communication from another party. This type of\ncomplexity measure has been studied under various names: advice complexity,\nKolmogorov complexity, distinguishing complexity, and instance complexity. We\npresent a general framework focusing on underlying combinatorial takes to study\nthese complexity measures using quantum information processing. We introduce\nthe key notions of relative hardness and quantum advantage, which provide the\nfoundations for task-based quantum minimal one-way information complexity\ntheory.",
    "arxiv_id": "quant-ph/0507270",
    "authors": [
      "Harumichi Nishimura",
      "Tomoyuki Yamakami"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Quantum Minimal One Way Information: Relative Hardness and Quantum   Advantage of Combinatorial Tasks",
    "url": "https://arxiv.org/abs/quant-ph/0507270"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "c906fd8e-8414-4145-88c7-e5a1aaaf6fc7",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}