Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups
<|reference_start|>Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups: In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_q$, 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 $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_p$, 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 $\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_p$.<|reference_end|>
@article{inui2004efficient,
    title={Efficient Quantum Algorithms for the Hidden Subgroup Problem over a
  Class of Semi-direct Product Groups},
    author={Yoshifumi Inui and Francois Le Gall},
    journal={Quantum Information and Computation, Vol. 7, No. 5&6 (2007),
  559-570},
    year={2004},
    doi={10.26421/QIC7.5-6-9},
    archivePrefix={arXiv},
    eprint={quant-ph/0412033},
    primaryClass={quant-ph cs.DS}
}