<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2018-09-29T17:51:50.783Z
Do you want the full result, or is it sufficient to sample from it?
Craig Gidney
CC BY-SA 4.0
2018-09-29T18:44:34.563Z
Thank you Craig Gidney for the comment. I updated the question.
Bassem Khoury
CC BY-SA 4.0
2018-09-30T17:00:00.540Z
I do not know about quantum algorithms, but if you allow some approximation this can be done classically faster than $O(n\log n)$ http://www.cs.utexas.edu/~ecprice/papers/hikp12.pdf.
Sasho Nikolov
<cc.complexity-theory><quantum-computing>
Efficient quantum algorithm for CLASSICAL FFT
Bassem Khoury
# Efficient quantum algorithm for CLASSICAL FFT

(Asked by: username_0 on 2018-09-28)

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.

**Tags:** cc.complexity-theory, quantum-computing
> **Comments:**
> **username_1**: Do you want the full result, or is it sufficient to sample from it?  
> **username_0**: Thank you Craig Gidney for the comment. I updated the question.  
> **username_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)$ http://www.cs.utexas.edu/~ecprice/papers/hikp12.pdf.  

---

## 0 answers

