量子フーリエ変換 (Quantum Fourier Transform) とは
https://whyitsso.net/physics/quantum_mechanics/QFT.html
＞これだけみると、おお、すごい！って感じです。しかし、量子状態の全ての係数を正確に取り出すには、指数関数的な時間がかかります。だから、単にFFTスペクトル全体を知りたい！というときには、普通に FFT を使って計算したほうが遥かにましです。でも、FFTのピーク位置だけ知りたい！というときには、QFTは有用です。なぜなら、周期的なデータに対してはその振動数に対応するある状態|k⟩の振幅だけが大きくなり、少しの測定でピーク位置を得ることができるからです。実は、Shorの素因数分解や、Groverの検索アルゴリズムなどの有名なアルゴリズムは、このとこをうまく使っているのです。