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$ – Pablo LiManni Oct 6 '19 at 1:55
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.