计算机科学 ›› 2018, Vol. 45 ›› Issue (6): 1-8.doi: 10.11896/j.issn.1002-137X.2018.06.001

• 综述 •    下一篇

隐含子群问题的研究现状

戴文静, 袁家斌   

  1. 南京航空航天大学计算机科学与技术学院 南京211106
  • 收稿日期:2017-05-09 出版日期:2018-06-15 发布日期:2018-07-24
  • 作者简介:戴文静(1992-),女,硕士生,主要研究方向为量子密码、量子计算,E-mail:jing@nuaa.edu.cn;袁家斌(1968-),男,博士后,教授,CCF高级会员,主要研究方向为信息安全、量子密码、高性能计算,E-mail:jbyuan@nuaa.edu.cn(通信作者)
  • 基金资助:
    本文受基于GPU集群的大规模量子线路仿真理论与方法研究(61571226),国家自然科学基金青年基金(61701229),江苏省自然科学基金青年基金(BK20170802)资助

Survey on Hidden Subgroup Problem

DAI Wen-jing, YUAN Jia-bin   

  1. College of Computer Science and Technology,Nanjing University of Aeronautics & Astronautics,Nanjing 211106,China
  • Received:2017-05-09 Online:2018-06-15 Published:2018-07-24

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

关键词: 量子计算, 隐含子群问题, 交换群, 二面体群, 唯一最短向量问题, 对称群

Abstract: 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.

Key words: Quantum computation, Hidden subgroup problem, Abelian group, Dihedral group, Unique shortest vector problem, Symmetric group

中图分类号: 

  • TP309.2
[1]DIFFIE W,HELLMAN M E.New directions in cryptography[J].IEEE Transactions on Information Theory,1976,22(6):644-654.
[2]RIVEST R L,SHAMIR A,ADLEMAN L.A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the Acm,1978,26(2):96-99.
[3]ELGAMAL T.A Public-Key Cryptosystem and SignatureSche-me Based on Discrete Logarithms[J].IEEE Transactions on Information Theory,1985,31(4):469-472.
[4]MILLER V S.Use of Elliptic Curves in Cryptography[M]//Advances in Cryptology-CRYPTO’85 Proceedings.Springer Berlin Heidelberg,1986:417-426.
[5]SHOR P W.Algorithms for Quantum Computation:Discrete Log and Factoring[C]//Proceedings of the 35th Symposium on Foundations of Computer Science.1994:124-134.
[6]GROVER L K.A fast quantum mechanical algorithm for database search[C]//ACM Symposium on the Theory of Computing.1996:212-219.
[7]WANG H F .Theoretical study on grover quantum search algorithm[D].Harbin:Harbin Institute of Technology,2010.(in Chinese)
王洪福.Grover量子搜索算法理论研究[D].哈尔滨:哈尔滨工业大学,2010.
[8]REGEV O.Quantum computation and lattice problems[C]//Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.2002:520-529.
[9]BRIGHT C.From the Shortest Vector Problem to the Dihedral Hidden Subgroup Problem[J/OL].https://cs.uwaterloo.ca/~cbright/reports/cs667proj.pdf.
[10]BERNSTEIN D J,BUCHMANN J,DAHMEN E.抗量子计算密码[M].张焕国,王后珍,杨昌,等译.北京:清华大学出版社,2015.
[11]DEUTSCH D.Quantum theory,the Church-Turing principle and the universal quantum computer[J].Proceedings of the Royal Society of London A,1985,400(1818):97-117.
[12]SIMON D R.On the power of quantum computation[C]//Symposium on Foundations of Computer Science.IEEE Computer Society,1994:116-123.
[13]KITAEV A Y.Quantum measurements and the Abelian stabilizer problem[OL].https://arxiv.org/abs/quant-ph/9511026.
[14]NIELSEN M A,CHUANG I L.量子计算和量子信息(一)--量子计算部分[M].赵千川,译.北京:清华大学出版社,2004.
[15]DAN B,LIPTON R J.Quantum Cryptanalysis of Hidden Linear Functions[C]//International Cryptology Conference on Advances in Cryptology.Springer-Verlag,1995:424-437.
[16]BRASSARD G,HØYER P.An Exact Quantum Polynomial-Time Algorithm for Simon’s Problem[C]//Israel Symposium on the Theory of Computing Systems.IEEE Computer Society,1997:12.
[17]JOZSA R.Quantum algorithms and the Fourier transform[C]//Proceedings of the Royal Society of London A:Mathematical,Physical and Engineering Sciences.1997:323-337.
[18]JOZSA R.Quantum Factoring.Discrete Logarithms,and the Hidden Subgroup Problem[J].Computing in Science & Engineering,2001,3(2):34-43.
[19]MOSCA M.Quantum computer algorithms[D].Oxford:University of Oxford,1999.
[20]MOSCA M,EKERT A.The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer[M]//Quantum Computing and Quantum Communications.Springer Berlin Heidelberg,1999:174-188.
[21]CHEUNG K K H,MOSCA M.Decomposing Finite Abelian Groups[J].Quantum Information & Computation,2001,1(3):26-32.
[22]SUN J.Dihedral Hidden Subgroup problem Based on Quantum Computing Algorithms[D].Nanjing:Nanjing University of Aero-nautics and Astronautics,2012.(in Chinese)
孙静.基于量子计算的二面体群隐含子群问题研究[D].南京:南京航空航天大学,2012.
[23]EKERT A,JOZSA R.Quantum Algorithms:Entanglement Enhanced Information Processing[J].Philosophical Transactions Mathematical Physical & Engineering Sciences,1998,356(1743):1769-1782.
[24]CLEVE R.The query omplexity of order-finding[C]//15th Annual IEEE Conference on Computational Complexity.IEEE,2000:54-59.
[25]ETTINGER M,HØYER P.On Quantum Algorithms for Noncommutative Hidden Subgroups[J].Advances in Applied Ma-thematics,1998,25(3):239-251.
[26]RÖETTELER M,BETH T.Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups[OL].https://arxiv.org/abs/quant-ph/9812070.
[27]PÜSCHEL M,RÖTTELER M,BETH T.Fast Quantum Fourier Transforms for a Class of Non-abelian Groups[J].Transactions of the American Mathematical Society,1999,362(2):1009-1045.
[28]BEALS R,BUHRMAN H,CLEVE R,et al.Quantum Lower Bounds by Polynomials[C]//Symposium on Foundations of Computer Science.IEEE Computer Society,1998:352.
[29]ETTINGER M,HOYER P,KNILL E.Hidden Subgroup States are Almost Orthogonal[OL].https://arxiv.org/abs/quant-ph/9901034.
[30]BERNSTEIN D J,BUCHMANN J,DAHMEN E.Post Quan-tum Cryptography[M].Berlin:Springer Berlin Heidelberg,2008.
[31]WANG F.The Hidden Subgroup Problem[OL].https://ar-xiv.org/abs/1008.0010.
[32]MURPHY J N.Analysing the quantum fourier transform for finite groups through the hidden subgroup problem[D].Québec:McGill University,2001.
[33]KUPERBERG G.A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem[J].Siam Journal on Computing,2003,35(1):170-188.
[34]REGEV O.A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space[J].Procee-dings of Annual Symposium on the Foundations of Computer Science,2004,64(1):124-134.
[35]KUPERBERG G.Another subexponential-time quantum algo-rithm for the dihedral hidden subgroup problem[OL].https://arxiv.org/abs/1112.3333.
[36]KOBAYASHI H,GALL F L.Dihedral Hidden Subgroup Problem :A Survey(Quantum Computation and Information)[J].Information & Media Technologies,2006,1(10):470-477.
[37]JIN G L,YUAN J B.Quantum Cloning-based Quantum Algo-rithm for Dihedral Hidden Subgroup Problem[J].ComputerScien-ce,2014,41(8):183-185.(in Chinese)
金广龙,袁家斌.基于量子克隆的二面体群隐含子群问题量子算法的研究[J].计算机科学,2014,41(8):183-185.
[38]LOMONACO S J,KAUFFMAN L H.Is Grover’s Algorithm a Quantum Hidden Subgroup Algorithm?[J].Quantum Information Processing,2007,6(6):461-476.
[39]BEALS R.Quantum computation of Fourier transforms over symmetric groups[C]//Twenty-Ninth ACM Symposium on the Theory of Computing.1997:48-53.
[40]MOORE C,RUSSELL A,SCHULMAN L J.The Symmetric Group Defies Strong Fourier Sampling[C]//IEEE Symposium on Foundations of Computer Science.IEEE Computer Society,2005:479-490.
[41]HALLGREN S,MOORE C,RUSSELL A,et al.Limitations of quantum coset states for graph isomorphism[C]//ACM Symposium on Theory of Computing.Seattle,Wa,USA,2006:604-617.
[42]KAWANO Y,SEKIGAWA H.Quantum fourier transform over symmetric groups[C]//International Symposium on Symbolic and Algebraic Computation.ACM,2013:227-234.
[43]IVANYOS G,MAGNIEZ F,SANTHA M.Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem[J].International Journal of Foundations of Computer Science,2003,14(5):723-739.
[44]FRIEDL K,IVANYOS G,MAGNIEZ F,et al.Hidden translation and orbit coset in quantum computing[C]//Proceedings of the thirty-fifth annual ACM symposium on Theory of computing.ACM,2003:1-9.
[45]INUI Y,GALL F L,et al.Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups[J].Quantum Information & Computation,2004,7(5):559-570.
[46]MOORE C,ROCKMORE D,RUSSELL A,et al.The power of basis selection in Fourier sampling:Hidden subgroup problems in affine groups[C]//Fifteenth Acm-Siam Symposium on Discrete Algorithms(SODA 2004).New Orleans,Louisiana,USA,2004:1113-1122.
[47]BACON D,CHILDS A M,DAM W V.From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups[C]//IEEE Symposium on Foundations of Computer Science,2005(FOCS 2005).IEEE Xplore,2005:469-478.
[48]MOORE C,ROCKMORE D,RUSSELL A,et al.The power of strong Fourier sampling:Quantum algorithms for affine groups and hidden shifts[J].SIAM Journal on Computing,2007,37(3):938-958.
[49]GONCALVES D N,PORTUGAL R.Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups[OL].https://arxiv.org/abs/1104.1361.
[50]CHIA N H,HALLGREN S.How hard is deciding trivial versus nontrivial in the dihedral coset problem?[OL].https://arxiv.org/abs/1608.02003.
[51]LI F,BAO W,FU X.A quantum algorithm for the dihedral hidden subgroup problem based on lattice basis reduction algorithm[J].Chinese Science Bulletin,2014,59(21):2552-2557.
[52]GOGIOSO S,KISSINGER A.Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem[OL].https://arxiv.org/abs/1701.08669.
[53]CHILDS A M.Lecture notes on quantum algorithms[OL].https://www.cs.umd.edu/~amchilds/qa.
[1] 罗文俊, 雷爽. 噪声信道下的盲量子计算[J]. 计算机科学, 2020, 47(7): 37-41.
[2] 周恒, 王拥军, 王宝山, 燕健. 直觉主义视角下量子逻辑的进一步解释[J]. 计算机科学, 2020, 47(5): 1-6.
[3] Renata WONG. 量子计算与不确定性原理[J]. 计算机科学, 2020, 47(1): 40-50.
[4] 张亮亮,张翌维,梁洁,孙瑞一,王新安. 新量子技术时代下的信息安全[J]. 计算机科学, 2017, 44(7): 1-7.
[5] 徐永振,郭躬德,蔡彬彬,林崧. 基于一维三态量子游走的量子聚类算法[J]. 计算机科学, 2016, 43(3): 80-83.
[6] 樊富有,杨国武,张 艳,杨 钢. 三值量子基本门及其对量子Fourier变换的电路实现[J]. 计算机科学, 2015, 42(7): 57-61.
[7] 王冬,刘强,李善治. 基于矩阵初等变换的量子可逆逻辑电路双向综合算法[J]. 计算机科学, 2014, 41(9): 18-23.
[8] 金广龙,袁家斌. 基于量子克隆的二面体群隐含子群问题量子算法的研究[J]. 计算机科学, 2014, 41(8): 183-185.
[9] 樊富有,杨国武,李晓瑜,罗庆斌. 混合多值可逆逻辑中广义Toffoli门仅用CNOT门的实现[J]. 计算机科学, 2014, 41(8): 115-117.
[10] 王冬,刘志昊,朱皖宁,李善治. 基于多目标扩展通用Toffoli门的量子比较器设计[J]. 计算机科学, 2012, 39(9): 302-306.
[11] 董青 吴楠. 整数质因子分解算法新进展与传统密码学面临的挑战[J]. 计算机科学, 2008, 35(8): 17-20.
[12] 缑水平 焦李成 田小林. 基于量子进化规划核聚类算法的图像分割[J]. 计算机科学, 2008, 35(7): 213-215.
[13] 钱辰. 量子纠缠和量子计算[J]. 计算机科学, 2006, 33(12): 230-234.
[14] 张云洁. 量子测量与量子计算[J]. 计算机科学, 2006, 33(10): 216-220.
[15] 苏运霖. 量子计算机的回顾与展望[J]. 计算机科学, 2002, 29(1): 17-20.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[3] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[4] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[5] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[6] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[7] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[8] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[9] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[10] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .