We give an algorithm for approximating the quantum Fourier transform over an arbitrary Z/sub p/ which requires only O(n log n) steps where n=log p to achieve an approximation to within an arbitrary inverse polynomial in n. This improves the method of A.Y. Kitaev (1995) which requires time quadratic in n. This algorithm also leads to a general and efficient Fourier sampling technique which improves upon the quantum Fourier sampling lemma of L. Hales and S. Hallgren (1997). As an application of this technique, we give a quantum algorithm which finds the period of an arbitrary periodic function, i.e. a function which may be many-to-one within each period. We show that this algorithm is efficient (polylogarithmic in the period of the function) for a large class of periodic functions. Moreover, using standard quantum lower-bound techniques, we show that this characterization is right. That is, this is the maximal class of periodic functions with an efficient quantum period-finding algorithm.

We isolate and generalize a technique implicit in many quantum algorithms, including Shor's algorithms for factoring and discrete log.In particular, we show that the distribution sampled after a Fourier transform over Zp can be efficiently approximated by transforming over Z, for any q in a large range.Our result places no restrictions on the superposition to be transformed, generalizing previous applications.In addition, our proof easily generalizes to multi-dimensional transforms for any constant number of dimensions.