{
  "annotation_id": "eceb9c0b-5762-4a39-993f-7f04c603381b",
  "date_created": "2026-03-02T18:02:03.308000Z",
  "date_modified": "2026-03-02T18:02:03.308000Z",
  "file_hash": "2ed4302097707fcf78f2cf813d7c542f0e64b1310bb444b91ce271e872ba6024",
  "private": false,
  "record": {
    "abstract": "We present a quantum algorithm which identifies with certainty a hidden\nsubgroup of an arbitrary finite group G in only a polynomial (in log |G|)\nnumber of calls to the oracle. This is exponentially better than the best\nclassical algorithm. However our quantum algorithm requires exponential time,\nas in the classical case. Our algorithm utilizes a new technique for\nconstructing error-free algorithms for non-decision problems on quantum\ncomputers.",
    "arxiv_id": "quant-ph/0401083",
    "authors": [
      "Mark Ettinger",
      "Peter Hoyer",
      "Emanuel Knill"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1016/j.ipl.2004.01.024",
    "journal_ref": "Information Processing Letters, 91(1), 43-48, 16 July 2004",
    "title": "The quantum query complexity of the hidden subgroup problem is   polynomial",
    "url": "https://arxiv.org/abs/quant-ph/0401083"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "e98d8362-0238-420f-9c21-117dbe5a85fa",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}