A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space

Research output: Contribution to journalArticlepeer-review


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.
Original languageUndefined
Article numberquant-ph/0406151
StatePublished - Jun 21 2004


  • quant-ph

Cite this