A quantum algorithm for the Hidden Subgroup Problem over the group Z/p^{r}Z \rtimes Z/q^{s}Z is presented. This algorithm, which for certain parameters of the group qualifies as 'efficient', generalizes prior work on related semi-direct product groups.
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups Zpr⋊Zq, for p and q prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form Zpr⋊Zp, where p is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups Zprm⋊Zp.
We present efficient quantum algorithms for the hidden subgroup problem (HSP) on the semidirect product of cyclic groups Zpr⋊ϕZp2, where p is any odd prime number and r is any integer such that r>4. We also address the HSP in the group ZN⋊ϕZp2, where N is an integer with a special prime factorization. These quantum algorithms are exponentially faster than any classical algorithm for the same purpose.
We characterize the algebraic structure of semi-direct product of cyclic groups, ZN⋊Zp, where p is an odd prime number which does not divide q−1 for any prime factor q of N, and provide a polynomial-time quantum computational algorithm solving hidden symmetry subgroup problem of the groups.
After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.