The dihedral hidden subgroup problem
arXiv:2106.09907 · doi:10.1515/jmc-2022-0029
Abstract
We give an exposition of the hidden subgroup problem for dihedral groups from the point of view of the standard hidden subgroup quantum algorithm for finite groups. In particular, we recall the obstructions for strong Fourier sampling to succeed, but at the same time, show how the standard algorithm can be modified to establish polynomial quantum query complexity. Finally, we explain a new connection between the dihedral coset problem and cloning of quantum states.
19 pages, expanded survey content and additional no-go theorems added