{
  "annotation_id": "7602676c-e952-40b1-86a5-fc057da758f8",
  "date_created": "2026-03-02T18:01:56.509000Z",
  "date_modified": "2026-03-02T18:01:56.509000Z",
  "file_hash": "1e52e5e57934660fcdb77240d9ad900f3556bed933aa236dc1bdd8a1d5289cbc",
  "private": false,
  "record": {
    "abstract": "We present a quantum algorithm for the dihedral hidden subgroup problem with\ntime and query complexity $O(\\exp(C\\sqrt{\\log N}))$. In this problem an oracle\ncomputes a function $f$ on the dihedral group $D_N$ which is invariant under a\nhidden reflection in $D_N$. By contrast the classical query complexity of DHSP\nis $O(\\sqrt{N})$. The algorithm also applies to the hidden shift problem for an\narbitrary finitely generated abelian group.\n  The algorithm begins with the quantum character transform on the group, just\nas for other hidden subgroup problems. Then it tensors irreducible\nrepresentations of $D_N$ and extracts summands to obtain target\nrepresentations. Finally, state tomography on the target representations\nreveals the hidden subgroup.",
    "arxiv_id": "quant-ph/0302112",
    "authors": [
      "Greg Kuperberg"
    ],
    "categories": [
      "quant-ph",
      "math.RT"
    ],
    "journal_ref": "SIAM J. Comput. 35 (2005), 170-188",
    "title": "A subexponential-time quantum algorithm for the dihedral hidden subgroup   problem",
    "url": "https://arxiv.org/abs/quant-ph/0302112"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "5729a9f4-cf74-452b-960c-1ad36972e03b",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}