Computer Science ›› 2014, Vol. 41 ›› Issue (8): 183-185.doi: 10.11896/j.issn.1002-137X.2014.08.040

Previous Articles     Next Articles

Quantum Cloning-based Quantum Algorithm for Dihedral Hidden Subgroup Problem

JIN Guang-long and YUAN Jia-bin   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Kuperberg presented a quantum algorithm for the dihedral hidden subgroup problem,but with sub-exponential time and query complexity.We presented a quantum cloning-based quantum algorithm for dihedral hidden subgroup problem with polynomial time and query complexity.Dihedral hidden subgroup problem is related to poly(n)-unique shortest vector problem.If the dihedral hidden subgroup problem is solved efficiently,the lattice-based cryptography can be breaken,which is secure against quantum computers.

Key words: Hidden subgroup problem,Dihedral group,Shortest vector problem,Quantum cloning,Linear polynomial

[1] Shor P.Algorithms for Quantum Computation:Discrete Log andFactoring [C]∥Proceedings of the 35th Symposium on Foundations of Computer Science.1994:124-134
[2] Ettinger M,Hoyer P,Knill E.Hidden subgroup states are almost orthogonal [J/OL].arXiv:quant-ph/9901034,1999
[3] Murphy J.Analysing the Quantum Fourier Transform for finite groups through the Hidden Subgroup Problem [D].Montreal:McGill University,2001
[4] Kuperberg G.A subexponential-time quantum algorithm for the dihedral hidden subgroup problem [J/OL].arXiv:quant-ph/0302112
[5] Regev O.Quantum computation and lattice problems [C]∥Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science.2002:520-529
[6] Regev O.A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space [J/OL].arXiv:quant-ph/0406151
[7] Childs A M,Jao D,Soukharev V.Constructing elliptic curve isogenies in quantum subexponential time [J/OL].arXiv:1012:4019
[8] Kuperberg G.Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem [J/OL].arXiv:1112.3333
[9] Wootters W K,Zurek W H.A single quantum cannot be cloned [J].Nature,1982,299:802-803
[10] Barnum H,Caves C M,Fuchs C A,et al.Non-commuting mixed states cannot be broadcast[J].Phys.Rev.Lett,1996,76:2818-2821
[11] Duan L M,Guo G C.Probabilistic cloning and identification of linearly independent quantum states [J].Phys.Rev.Lett,1998,80(22):4999-5002
[12] Pati A K.Quantum superposition of multiple clones and the novel cloning machine [J].Phys.Rev.Lett,1999(83):2849-2852

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!