论文标题
确切的量子隐藏子组算法和可解决组的应用
An exact quantum hidden subgroup algorithm and applications to solvable groups
论文作者
论文摘要
我们为隐藏子组问题$ z_ {m^k}^n $提供了一个多项式时间精确量子算法。该算法使用量子傅立叶变换模量M，并且不需要M的分解。对于光滑的m，即，当M的素数为大小（log M）时，可以使用Cleve和Coppersmith独立发现的方法来精确地计算量子傅立叶变换，而对于一般M，Mosca和Zalka的算法可用。即使在M = 3和K = 1中，我们的结果似乎是新的。我们还提出了用于计算Abelian和可解决的群体的结构的应用，其顺序的主要因素（但可能是未知）与M相同（但可能是未知）。可解决的组的应用还依赖于Watrous提出的技术的精确版本来计算亚组元素的均匀叠加。
We present a polynomial time exact quantum algorithm for the hidden subgroup problem in $Z_{m^k}^n$. The algorithm uses the quantum Fourier transform modulo m and does not require factorization of m. For smooth m, i.e., when the prime factors of m are of size poly(log m), the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general m, the algorithm of Mosca and Zalka is available. Even for m=3 and k=1 our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as m. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.
