量子コンピュータでフーリエ変換すると高速フーリエ変換より高速な件 - Qiita離散フーリエ変換？ 離散フーリエ変換とは、フーリエ変換を離散化したものです。おしまい（ぉぃ ……えーと、みんな大好き周波数分解をするためのもので、音声処理とか画像処理とか無線通信とか色々なところで目にする偉いやつです。式はこんな感じです。 \begin{pmatrix} y_{0} \\ y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \\ y_{5} \\ y_{6} \\ y_{7} \\ \end{pmatrix} = \begin{pmatrix} w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} & w^{0} \\ w^{0} & w^{1} & w^{2} & w^{3} & w^{4} & w^{5} & w^{6} & w^{7} \\ w^{0} & w^{2} & w^{4} & w^{6}
