  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 ${\mathbb
Z}_p$ can be efficiently approximated by transforming over ${\mathbb Z}_q$ for
any q in a large range. Our result places no restrictions on the superposition
to be transformed, generalizing the result implicit in Shor which applies only
to periodic superpositions. In addition, our proof easily generalizes to
multi-dimensional transforms for any constant number of dimensions.
