1998/12/21 by Lisa Hales, Hales, Lisa, Sean Hallgren +1
Computer Science · Physics and Astronomy · #Neural Networks and Applications #Numerical Methods and Algorithms #Quantum Computing Algorithms and Architecture #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9812060
17 pages. Preliminary draft
arxiv created 1998/12/21 · arxiv updated 2009/12/01
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 Zp can be efficiently approximated by transforming over \mathbb Zq 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.