A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
classification
🪐 quant-ph
keywords
algorithmspacesubexponentialtimedihedralhiddenpolynomialproblem
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.