Quantum Algorithms For The Dihedral Hidden Subgroup Problem

Shor presented a polynomial quantum algorithm for factoring integers. And the RSAcryptosystem is based on the hardness of factoring integers. Shor also gave a polynomial quantumalgorithm solving the discrete logarithm problem, which used in several other cryptosystems. The twoalgorithms fit in a framework which is called the hidden subgroup problem. Similarly, poly(n)-uniqueshortest vector problem which is used in some lattice-based cryptosystem can be explained as thedihedral hidden subgroup problem. If the unique shortest vector problem could be solved efficiently,one could break the lattice-based cryptosystem. It found that abelian hidden subgroup problem can besolved by quantum computer exponentially faster than their classical counterparts. But fornon-abelian hidden subgroup, quantum algorithms are not so quite satisfied. So far, the abelian hiddensubgroup problem is solved and most researches are focus on the two non-abelian groups, dihedralgroup and symmetric group. A quantum algorithm for symmetric hidden subgroup problem can beused for determining graph isomorphism.In this paper, we present quantum algorithms for DHSP. Regev described a quantum algorithmfor DHSP which is considered as the best quantum algorithm so far. We optimize the quantumalgorithm and analyze computational complexity. And we present another quantum algorithm forDHSP which is based on distinctness of ensembles having the density matrix. And we present twoquantum algorithms for DHSP which are based on probabilistic quantum cloning. In the end, wesimulate these algorithms and analyze the quantum algorithm’s performance.