3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What is a quantum Fourier transform? I believe the same mathematical process applies in the classical and quantum cases. $\endgroup$
    – probably_someone
    Commented Dec 31, 2016 at 11:36
  • 2
    $\begingroup$ 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! $\endgroup$
    – Norbert Schuch
    Commented Jan 1, 2017 at 13:42
  • $\begingroup$ @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!) $\endgroup$
    – Rufus
    Commented Jan 2, 2017 at 8:34
  • $\begingroup$ I don't understand your comment. What is a time-value pair? Or a superposition-amplitude pair? $\endgroup$
    – Norbert Schuch
    Commented Jan 2, 2017 at 13:28
  • $\begingroup$ See quantumcomputing.stackexchange.com/q/4424/8754 and answers within $\endgroup$
    – BjornW
    Commented Jun 10, 2022 at 9:34

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ I don't think this answers the OPs full question, in particular, the key issue in QFT is how to make use of the output (the OPs last section). I.e. how can you use what you gained of the actual QFT itself. $\endgroup$
    – BjornW
    Commented Jun 9, 2022 at 13:10
  • $\begingroup$ Well, that's the problem with questions asking more than one question. $\endgroup$
    – Norbert Schuch
    Commented Jun 9, 2022 at 22:12
  • $\begingroup$ Absolutely, the question did ask for how it's implemented. It's just that I was researching the same question and it seems to me that the "usage" part is the difficult part, as you can't "read out" the result straight out so the fact that it's built with less operations than the classical counterpart feels like only a part of the explanation. $\endgroup$
    – BjornW
    Commented Jun 10, 2022 at 9:20
  • $\begingroup$ @BjornW If you want to understand how it is used, have a look at Shor's algorithm (or rather, the period-finding part of Shor's algorithm). $\endgroup$
    – Norbert Schuch
    Commented Jun 10, 2022 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.