Quantum Fourier sampling simplified
Lisa Hales, Sean Hallgren · 1999
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.