Dihedral Hidden Subgroup Problem: A Survey (特集:量子計算と量子情報)

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 一般社団法人情報処理学会の論文
• 2005-10-15

著者

• Gall Francois

  Department Of Computer Science Graduate School Of Information Science And Technology The University

• KOBAYASHI HIROTADA

  Foundations of Information Research Division, National Institute of Informatics

• Kobayashi Hirotada

  Foundations Of Information Research Division National Institute Of Informatics:quantum Computation And Information Project Exploratory Research For Advanced Study Japan Science And Technology Agency

• Le Gall

  Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo

関連論文

• Dihedral Hidden Subgroup Problem: A Survey (特集:量子計算と量子情報)
• Dihedral Hidden Subgroup Problem: A Survey
• Faster Algorithms for Rectangular Matrix Multiplication

スポンサーリンク