up vote 6 down vote favorite

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.

share|cite|improve this question
  • 2
    Do you want the full result, or is it sufficient to sample from it? – Craig Gidney Sep 29 at 17:51
  • Thank you Craig Gidney for the comment. I updated the question. – Bassem Khoury Sep 29 at 18:44
  • 2
    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 at 17:00

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.