An Efficient Quantum Algorithm for the Hidden Subgroup Problem over a Class of Semidirect Product Groups
An Efficient Quantum Algorithm for the Hidden Subgroup Problem over a Class of Semidirect Product Groups
复制标题
一类半直积群上隐藏子群问题的高效量子算法
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
F. Gall
中科院分区：
文献类型：
--
作者：
Yoshifumi Inui;F. Gall
本文研究半直积群类Zn <$Zq上的隐子群问题。半直积的定义取决于同态的选择，我们首先分析了这种同态在n和q的函数中的不同可能性。然后，我们提出了一个多项式时间量子算法求解形式为Zpr <$Zp的群上的HSP，其中p是奇素数，最后将其推广到群类Zpr <$Zp。
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups Zn ⋊ Zq. The definition of the semi-direct product depending on the choice of an homomorphism, we first analyze the different possibilities for this homomorphism in function of n and q. Then, we present a polynomial-time quantum algorithm solving the HSP over the groups of the form Zpr ⋊ Zp, where p is an odd prime, and finally extend it to the class of groups Zpr ⋊ Zp.