Computer Science ›› 2018, Vol. 45 ›› Issue (6): 1-8.doi: 10.11896/j.issn.1002-137X.2018.06.001

• Surveys •     Next Articles

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

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

CLC Number: 

  • 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] ZHANG Liang-liang, ZHANG Yi-wei, LIANG Jie, SUN Rui-yi and WANG Xin-an. Information Security in New Quantum Technology Age [J]. Computer Science, 2017, 44(7): 1-7, 15.
[2] XU Yong-zhen, GUO Gong-de, CAI Bin-bin and LIN Song. Quantum Clustering Algorithm Based on One-dimensional Three-state Quantum Walk [J]. Computer Science, 2016, 43(3): 80-83.
[3] FAN Fu-you, YANG Guo-wu, ZHANG Yan and YANG Gang. Three-valued Quantum Elementary and Implementation of Quantum Fourier Transform Circuit [J]. Computer Science, 2015, 42(7): 57-61.
[4] WANG Dong,LIU Qiang and LI Shan-zhi. Bidirectional Reversible Logic Circuit Synthesis Algorithm Based on Matrix Elementary Transformation [J]. Computer Science, 2014, 41(9): 18-23.
[5] JIN Guang-long and YUAN Jia-bin. Quantum Cloning-based Quantum Algorithm for Dihedral Hidden Subgroup Problem [J]. Computer Science, 2014, 41(8): 183-185,218.
[6] FAN Fu-you,YANG Guo-wu,LI Xiao-yu and LUO Qing-bin. Realization of Toffoli Gate Only Using CNOT Gate in Hybrid Multi-value Reversible Logic [J]. Computer Science, 2014, 41(8): 115-117,134.
[7] . Design of Quantum Comparator Based on Extended General Toffoli Gates with Multiple Targets [J]. Computer Science, 2012, 39(9): 302-306.
[8] ZHAO Xiu-feng,XU Qiu-liang, LIU wei. Asymmetric Group Key Agreement with Traitor Traceability [J]. Computer Science, 2011, 38(9): 41-44.
[9] FEI Ding-zhou (Department of Psychology, Wuhan University, Wuhan 430072, China). [J]. Computer Science, 2009, 36(4): 56-59.
[10] GOU Shui-ping JIAO Li-cheng TIAN Xiao-lin (Institute of Intelligent Information Proeessing,Xidian University,Xi'an 710071,China). [J]. Computer Science, 2008, 35(7): 213-215.
[11] QIAN Chen (State Key Laboratory for Novel Software Technology,Department of Computer Science and Technology Nanjing University,Najing 210093). [J]. Computer Science, 2006, 33(12): 230-234.
[12] ZHANG Yun-Jie (State Key Laboratory for Novel Software Technology, Department of Computer Science and Technology, Nanjing University,Nanjing 210093). [J]. Computer Science, 2006, 33(10): 216-220.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[3] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[4] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[5] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[6] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[7] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[8] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[9] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[10] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .