Understand Shor's Algorithm & Quantum Fourier Transform

[michael879]

hey, from what I've read here: http://www.quantiki.org/wiki/index.php/Shor%27s_Algorithm , I understand most of the algorithm. The one thing that I don't get is what the quantum Fourier transform does to the input register. Can someone either explain how this works or what exactly it does?

 

[genneth]

Perhaps this helps: http://scottaaronson.com/blog/?p=208

 

[michael879]

thanks, that was pretty helpful. However there is almost no math or quantum mechanics in that article. All I understood was his metaphor for the QFT, not really the DFT.