# 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. – probably_someone Dec 31 '16 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! – Norbert Schuch Jan 1 '17 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!) – Rufus Jan 2 '17 at 8:34
• I don't understand your comment. What is a time-value pair? Or a superposition-amplitude pair? – Norbert Schuch Jan 2 '17 at 13:28

## 1 Answer

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).