# Efficient quantum algorithm for CLASSICAL FFT

Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples.

I need to find the amplitude and phase of the K dominating (highest amplitude) frequencies, where K is a fixed constant and K is much smallet then n.

• Do you want the full result, or is it sufficient to sample from it? – Craig Gidney Sep 29 '18 at 17:51
• Thank you Craig Gidney for the comment. I updated the question. – Bassem Khoury Sep 29 '18 at 18:44
• I do not know about quantum algorithms, but if you allow some approximation this can be done classically faster than $O(n\log n)$ cs.utexas.edu/~ecprice/papers/hikp12.pdf. – Sasho Nikolov Sep 30 '18 at 17:00