Hi there everyone. I thought this was as good a place to ask this as any, so here’s the problem:
can anyone explain to me (or refer me to somewhere where it is explained) how you can calculate a Fast Fourier Transform on a quantum computer? I’ve got one or two theses that mention it, but neither is particularly clear. Thanks in advance. 
PS if you want to play around with a quantum computer emulator, you can download it from here
A quick google search on “fft quantum computer” turned up this paper, which gives a couple references that may be helpful. You might also want to look through the other search results.
Welcome to the boards.
Thanks. I already tried google for searching for various combinations of fft, fast fourier transform, quantum computer etc., and I found a few useful and some not so useful results. I don’t think I’ve seen this one before though, so I’ll print it and check it out in the near future.
There’s a book called “Quantum Computation and Quantum Information” by Nielsen and Chuang that has a whole chapter on the quantum Fourier transform. That might help.
http://www.scirus.com/search_simple/?frm=simple&query_1=Quantum+Computers&ds=mem
from the scientific information search engine at
Here’s another reference (this is the home page of a Caltech course on quantum computation; the quantum Fourier transform is discussed in Chapter 6 of the course notes, starting on page 72). The rest of the notes are good too; some of the preceding sections outline an important application of the QFT.
Note that there’s a fundamental difference (besides the increased speed of the quantum version) between the FFT performed on a classical computer and the quantum Fourier transform. In the classical FFT, you have a list of N complex values in memory; taking the FFT gives another vector of length N. In particular, after taking the FFT you know all N values of this vector. In the quantum Fourier transform, the N complex values are coefficients of the basis-state expansion of a quantum state, so you don’t in general know all of the values. Measuring the state can tell you (probabilistically) some information about the values, but to determine the whole vector would require performing the QFT multiple times.