Oded Regev
Published 2004-06-21Version 1
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.
Comments: 7 pages, 1 figure
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem
Optimal measurements for the dihedral hidden subgroup problem
A quantum algorithm for the dihedral hidden subgroup problem based on algorithm SV
