iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.11185/IMT.1.178
Dihedral Hidden Subgroup Problem: A Survey
Information and Media Technologies
Online ISSN : 1881-0896
ISSN-L : 1881-0896
Computing
Dihedral Hidden Subgroup Problem: A Survey
Hirotada KobayashiFrançois Le Gall
Author information
JOURNAL FREE ACCESS

2006 Volume 1 Issue 1 Pages 178-185

Details
Abstract

After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.

Content from these authors
© 2006 by Information Processing Society of Japan
Previous article Next article
feedback
Top