戴文静,袁家斌.隐含子群问题的研究现状[J].计算机科学,2018,45(6):1-8
隐含子群问题的研究现状
Survey on Hidden Subgroup Problem
投稿时间:2017-05-09  修订日期:2017-08-11
DOI:10.11896/j.issn.1002-137X.2018.06.001
中文关键词:  量子计算,隐含子群问题,交换群,二面体群,唯一最短向量问题,对称群
英文关键词:Quantum computation,Hidden subgroup problem,Abelian group,Dihedral group,Unique shortest vector problem,Symmetric group
基金项目:本文受基于GPU集群的大规模量子线路仿真理论与方法研究(61571226),国家自然科学基金青年基金(61701229),江苏省自然科学基金青年基金(BK20170802)资助
作者单位E-mail
戴文静 南京航空航天大学计算机科学与技术学院 南京211106 jing@nuaa.edu.cn 
袁家斌 南京航空航天大学计算机科学与技术学院 南京211106 jbyuan@nuaa.edu.cn 
摘要点击次数: 304
全文下载次数: 236
中文摘要:
      在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.
查看全文  查看/发表评论  下载PDF阅读器