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

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? Oct 5 '19 at 1:28
• @MarkS: But FFT is not the classical version of QFT is it? 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.. Oct 6 '19 at 3:16
• 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)? Mar 20 '21 at 20:49