  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.

Quantum Physics;Computational Complexity