What is the cost of implementing the Quantum Fourier transform (QFT) in a classical computer? We know we require at least $\log{n}$ depth quantum circuits to do a QFT in a quantum computer, with $n$ being the number of input qubits. Is there a similar result for classical computers?

  • 1
    $\begingroup$ Have you reviewed en.wikipedia.org/wiki/Fast_Fourier_transform? $\endgroup$
    – Mark S
    Oct 5 '19 at 1:28
  • $\begingroup$ @MarkS: But FFT is not the classical version of QFT is it? $\endgroup$ Oct 6 '19 at 1:55
  • 1
    $\begingroup$ Yes, to run a classical version of, say, Shors algorithm, you could evaluate the periodic function for random inputs a number of times and hope for a collision, and use that collision to estimate the period. That would take exponential time.. $\endgroup$
    – Mark S
    Oct 6 '19 at 3:16
  • $\begingroup$ I'm voting to close because the question currently lacks sufficient detail. For example, is the input classical or quantum? Is the objective to simulate QFT on a classical computer or is the goal to compute the Fourier Transform of some input sequence (the "Quantum" in "Quantum Fourier Transform" suggests the former, but the letter is more useful)? $\endgroup$ Mar 20 '21 at 20:49