{
  "annotation_id": "785569df-3021-4a37-b09a-33fc63b18cbb",
  "date_created": "2026-03-02T18:02:27.566000Z",
  "date_modified": "2026-03-02T18:02:27.566000Z",
  "file_hash": "bf35b5a617be7cd95aeced02dc8b1a34eeaaf5654f50a22a52bf08748e940db3",
  "private": false,
  "record": {
    "abstract": "One of the central issues in the hidden subgroup problem is to bound the\nsample complexity, i.e., the number of identical samples of coset states\nsufficient and necessary to solve the problem. In this paper, we present\ngeneral bounds for the sample complexity of the identification and decision\nversions of the hidden subgroup problem. As a consequence of the bounds, we\nshow that the sample complexity for both of the decision and identification\nversions is $\\Theta(\\log|\\HH|/\\log p)$ for a candidate set $\\HH$ of hidden\nsubgroups in the case that the candidate subgroups have the same prime order\n$p$, which implies that the decision version is at least as hard as the\nidentification version in this case. In particular, it does so for the\nimportant instances such as the dihedral and the symmetric hidden subgroup\nproblems. Moreover, the upper bound of the identification is attained by the\npretty good measurement. This shows that the pretty good measurement can\nidentify any hidden subgroup of an arbitrary group with at most $O(\\log|\\HH|)$\nsamples.",
    "arxiv_id": "quant-ph/0604174",
    "authors": [
      "Masahito Hayashi",
      "Akinori Kawachi",
      "Hirotada Kobayashi"
    ],
    "categories": [
      "quant-ph"
    ],
    "journal_ref": "Quantum Information and Computation, 8, 0345-0358 (2008)",
    "title": "Quantum Measurements for Hidden Subgroup Problems with Optimal Sample   Complexity",
    "url": "https://arxiv.org/abs/quant-ph/0604174"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "2ba0d253-83e6-4b5f-a610-633178f9158c",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}