隐含子群问题的研究现状

Survey on Hidden Subgroup Problem

在Shor发现大整数因子分解问题的有效量子算法之后,量子计算迫使我们重新审视现有的密码系统。隐含子群问题是量子计算在群结构上的推广,它暗示通过考虑不同的群和函数来解决更困难的问题,以期找到新的指数倍快于其经典对应物的量子算法。有限交换群隐含子群问题的研究已有相对固定的研究框架和方法,而非交换群隐含子群问题的研究一直很活跃。研究表明,二面体群隐含子群问题的有效解决可能攻破基于格的唯一最短向量问题的密码体制,图同构问题可以转化为对称群隐含子群问题。文中对隐含子群问题的研究现状进行综述,希望能够吸引更多研究者对隐含子群问题的注意。最后为隐含子群问题未来的研究方向提出参考意见。

After Shor has presented an effective quantum algorithm for factoring of large integer,quantum computation forces us to re-examine the existing cryptosystems.Hidden subgroup problem is the generalization of quantum computation in group structure,it implicits that more difficult problems might be solved by considering various groups and functions to find new algorithms which are exponentially faster than their classical counterparts.The abelian hidden subgroup problem research has formed a relatively unified framework,while the non-abelian hidden subgroup problem research is always alive.The dihedral hidden subgroup problem may break the cryptosystems of the unique shortest vector problem based on the lattice and the graph isomorphism problem can be reduced to the symmetric hidden subgroup problem.The hidden subgroup problem was summarized to attract more researchers.Finally,this paper provided a suggestion for the direction of future research.