Bibliographic Information
- Other Title
-
- 招待論文
Search this article
Description
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.
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.
Journal
-
- 情報処理学会論文誌
-
情報処理学会論文誌 46 (10), 2409-2416, 2005-10-15
東京 : 情報処理学会
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1050564287836040448
-
- NII Article ID
- 110002769889
-
- NII Book ID
- AN00116647
-
- ISSN
- 18827764
- 03875806
-
- NDL BIB ID
- 7490451
-
- Text Lang
- en
-
- Article Type
- journal article
-
- Data Source
-
- IRDB
- NDL
- CiNii Articles