{
  "annotation_id": "214c6411-2c63-4e58-a6bc-fc71a50900f5",
  "date_created": "2026-03-02T18:02:20.033000Z",
  "date_modified": "2026-03-02T18:02:20.033000Z",
  "file_hash": "d5434e2ce5cc042571868a15860ed3e0be224d576b33157dfc9ba30f9b739307",
  "private": false,
  "record": {
    "abstract": "Consider the following generalized hidden shift problem: given a function f\non {0,...,M-1} x Z_N satisfying f(b,x)=f(b+1,x+s) for b=0,1,...,M-2, find the\nunknown shift s in Z_N. For M=N, this problem is an instance of the abelian\nhidden subgroup problem, which can be solved efficiently on a quantum computer,\nwhereas for M=2, it is equivalent to the dihedral hidden subgroup problem, for\nwhich no efficient algorithm is known. For any fixed positive epsilon, we give\nan efficient (i.e., poly(log N)) quantum algorithm for this problem provided M\n\u003e N^epsilon. The algorithm is based on the \"pretty good measurement\" and uses\nH. Lenstra\u0027s (classical) algorithm for integer programming as a subroutine.",
    "arxiv_id": "quant-ph/0507190",
    "authors": [
      "Andrew M. Childs",
      "Wim van Dam"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1145/1283383.1283515",
    "journal_ref": "Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007),\n  pp. 1225-1234",
    "title": "Quantum algorithm for a generalized hidden shift problem",
    "url": "https://arxiv.org/abs/quant-ph/0507190"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "18bf7a73-2bd2-4a66-90dd-798d27090e2f",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}