# What do the results of a quantum fourier transform describe?

The classical discrete fourier transform takes a sequence of values and outputs another sequence of values that describe a set of coefficients for complex sinusoids which can be used to reconstruct (or approximate) the original input.

In contrast, what exactly does a quantum fourier transform do? And how is it said to be the "analogue" of the discrete fourier transform?

More specifically, since all the input qubits are in superposition with each other, is there still the notion of an ordered sequence as there is in DFT (since the order of the inputs of DFT clearly affects the output)?

And how does one interpret the output of QFT? Say the output of a QFT is a superposition of $a |00\rangle +b|01\rangle + c|10\rangle + d|11\rangle$, what does this tell me about the original superposition?

• What is a quantum Fourier transform? I believe the same mathematical process applies in the classical and quantum cases. Dec 31, 2016 at 11:36
• The quantum Fourier transform applies a discrete Fourier transform to the amplitudes in a superposition. Does this answer your question? If not, you should make more precise what you are looking for! Jan 1, 2017 at 13:42
• @NorbertSchuch so does that mean the time - value pair in the case of DFT (usually), is translated to the superposition in QFT and the superposition - amplitude pair in QFT? (That was a very useful revelation!) Jan 2, 2017 at 8:34
• I don't understand your comment. What is a time-value pair? Or a superposition-amplitude pair? Jan 2, 2017 at 13:28
• See quantumcomputing.stackexchange.com/q/4424/8754 and answers within Jun 10, 2022 at 9:34

The quantum Fourier transform applies a discrete Fourier transform to the amplitudes in a superposition. This is, if your input is $$\sum a_n |n\rangle\ ,$$ then the output is $$\sum \hat a_n |n\rangle\ ,$$ where the vector $(\hat a_n)$ is the discrete Fourier transform of the vector $(a_n)$.
The point is that if $|n\rangle$ is encoded in binary (i.e., in a $N$-qubit register, with $n=2^N$), this can be carried out very efficiently, namely in time $O(N^2) = O((\log n)^2$), which is exponentially faster than classically (where $O(n\log n)$ operations are required).