Quick summary: Except a special class of quantum states where quantum Fourier transform can exponentially speedup, in general it is not faster than classical Fourier transform. Definition of classical Fourier transform \( \def\ket#1{{ \left| #1 \right> }} \) \( \def\bracket#1{{ \left( #1 \right) }} \) A discrete Fourier transform (DFT) of a $2^n$-length vector $x= \left( x_0, x_1, \ldots, x_{2^n..
Physics Corner 2022. 7. 16. 22:46
Quick summary: Except a special class of quantum states where quantum Fourier transform can exponentially speedup, in general it is not faster than classical Fourier transform. Definition of classical Fourier transform \( \def\ket#1{{ \left| #1 \right> }} \) \( \def\bracket#1{{ \left( #1 \right) }} \) A discrete Fourier transform (DFT) of a $2^n$-length vector $x= \left( x_0, x_1, \ldots, x_{2^n..