# What is the cost of implementing the Quantum Fourier transform in a classical computer?

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?

• Have you reviewed en.wikipedia.org/wiki/Fast_Fourier_transform? – Mark S Oct 5 '19 at 1:28
• @MarkS: But FFT is not the classical version of QFT is it? – Pablo LiManni Oct 6 '19 at 1:55
• 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.. – Mark S Oct 6 '19 at 3:16