4 ms·
The interesting part for signal processing is that you can run the discrete Fourier transform QFT [1] in O((log N)^2) time. It's much faster than the classic Fa
by gus_massa 7y ago
The interesting part for signal processing is that you can run the discrete Fourier transform QFT [1] in O((log N)^2) time. It's much faster than the classic Fast Fourier Transform that is O(N log N), that is much faster than the naïve calculation of the Fourier Transform that is O(N^2). https://en.wikipedia.org/wiki/Quantum_Fourier_transform https://en.wikipedia.org/wiki/Quantum_Fourier_transform
You get an extremely fast Fourier Transform, but for signal processing the problem is how to enter the data and how to extract the data.
In the Shor's algorithm the initial vale is easy to construct so you don't need O(N) time just to enter the data, and the output that you need to read is only a value, not all the values for every frequency, so you don't need O(N) time just to extract the data. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm
[1] I prefer to call it QFFT because the method is more similar to the FFT than to the FT, but most of the people disagree with me.