Fourier Sampling Arbitrary Periodic Functions

Lisa Hales

We exhibit a relationship between the Quantum Fourier Transforms of a fixed superposition over different cyclic groups, generalizing results implicit in Shor's Factoring and Discrete Log Algorithms. This generalization simplifies the proof of several existing algorithms, including Shor's. Moreover, we use it to give a new algorithm which efficiently computes the period of a large class of periodic functions, thus extending Shor's result, which applies only to functions which are one-to-one on their fundamental domains. Using standard lower bound techniques we also show this class is maximal.

created Thu Mar 2 11:21:29 PST 2000