{
  "id": "quant-ph/0406151",
  "version": "v1",
  "published": "2004-06-21T20:54:57.000Z",
  "updated": "2004-06-21T20:54:57.000Z",
  "title": "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space",
  "authors": [
    "Oded Regev"
  ],
  "comment": "7 pages, 1 figure",
  "categories": [
    "quant-ph"
  ],
  "abstract": "In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We describe a modified algorithm whose running time is still subexponential and whose space requirement is only polynomial.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-06-21T20:54:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "dihedral hidden subgroup problem",
      "polynomial space",
      "first subexponential time algorithm",
      "space requirement"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004quant.ph..6151R"
    }
  }
}