6
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Do you want the full result, or is it sufficient to sample from it? $\endgroup$ – Craig Gidney Sep 29 '18 at 17:51
  • $\begingroup$ Thank you Craig Gidney for the comment. I updated the question. $\endgroup$ – Bassem Khoury Sep 29 '18 at 18:44
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Sep 30 '18 at 17:00

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.