# Anyone familiar with quantum computers? **URL:** \ **Category:** Factual Questions\ **Created:** [January 4, 2003, 7:07pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641 "2003-01-04T19:07:59Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![Mr.Bas](https://avatars.discourse-cdn.com/v4/letter/m/9dc877/32.png) [@Mr.Bas](https://boards.straightdope.com/u/Mr.Bas)\ **Post date:** [January 4, 2003, 7:07pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641/1 "2003-01-04T19:07:59Z")
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](http://rugth30.phys.rug.nl/compphys0/qce.htm) ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [January 4, 2003, 8:14pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641/2 "2003-01-04T20:14:19Z")
A quick google search on “fft quantum computer” turned up [this paper](http://theorie5.physik.unibas.ch/proseminar/zalka.pdf), which gives a couple references that may be helpful. You might also want to look through the other search results. Welcome to the boards. ---
**Author:** ![Mr.Bas](https://avatars.discourse-cdn.com/v4/letter/m/9dc877/32.png) [@Mr.Bas](https://boards.straightdope.com/u/Mr.Bas)\ **Post date:** [January 4, 2003, 9:17pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641/3 "2003-01-04T21:17:46Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [January 4, 2003, 9:23pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641/4 "2003-01-04T21:23:14Z")
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. ---
**Author:** ![Azael](https://avatars.discourse-cdn.com/v4/letter/a/a8b319/32.png) [@Azael](https://boards.straightdope.com/u/Azael)\ **Post date:** [January 4, 2003, 9:44pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641/5 "2003-01-04T21:44:43Z")
[http://www.scirus.com/search\_simple/?frm=simple&query\_1=Quantum+Computers&ds=mem](http://www.scirus.com/search_simple/?frm=simple&query_1=Quantum+Computers&ds=mem) from the scientific information search engine at [http://www.scirus.com/](http://www.scirus.com/) ---
**Author:** ![Omphaloskeptic](https://avatars.discourse-cdn.com/v4/letter/o/bcef8e/32.png) [@Omphaloskeptic](https://boards.straightdope.com/u/Omphaloskeptic)\ **Post date:** [January 5, 2003, 7:38pm UTC](https://boards.straightdope.com/t/anyone-familiar-with-quantum-computers/146641/6 "2003-01-05T19:38:39Z")
Here’s [another reference](http://www.theory.caltech.edu/people/preskill/ph229/) (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.