量子フーリエ変換

古典的な高速フーリエ変換がN log N程度の演算を要するのに対し、量子版は量子ビット数の二乗程度で済む。データ量に対して指数的に少ないステップ数である。ただし変換後に残るのは直接覗けない振幅であり、観測すれば結果は一つしか得られない。

威力を発揮するのは、個々の値ではなく周期性を知りたいときだ。ショアのアルゴリズムはまさにそこを突いている。素因数分解は関数の周期を求める問題に帰着でき、この変換により数回の実行で高い確率で答えが得られる。