変なアナロジーですが、フーリエ変換はこの世界の双対な裏面の様な気もします。 話は、量子コンピュータに飛びますが、これで意味にある計算結果が取れるとは、全く信じられませんでした。 Shorの発見した、アルゴリズム（因数分解に使えるらしい）も、フーリエ変換の様な事をやってませんでしたっけ？
はい、Shorのアルゴリズムでは「量子フーリエ変換」が中心的な役割を果たします。重ね合わせから、測定できる計算結果をどう取り出すのかを、周期を見つける仕組みに沿って説明します。
はい、まさに量子フーリエ変換を使っています。「重ね合わせを作っても、測ったら一つしか出ない。それでどうやって有用な答えを得るのか」という疑問に、Shorのアルゴリズムは具体的な答えを与えています。
鍵は、個々の計算結果を全部読み出す必要はなく、結果全体に潜む「周期」を取り出せればよい、ということです。IBMの解説
まず、因数分解がなぜ周期の問題になるのかを見ます。例えば15を因数分解するために、
$$ f(x)=2^x\bmod 15 $$
つまり「$2^x$を15で割った余り」を考えます。
| $x$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| $f(x)$ | 1 | 2 | 4 | 8 | 1 | 2 | 4 | 8 | 1 |
周期は $r=4$ です。この周期が分かれば、
$$ 2^4-1=(2^2-1)(2^2+1)=3\times5 $$
から因数につながります。一般には、適切な条件を満たす周期 $r$ を得て、
$$ \gcd(a^{r/2}-1,N),\qquad \gcd(a^{r/2}+1,N) $$
を普通のコンピュータで計算します。うまくいかない場合は $a$ を変えて試します。難しい部分を「巨大な数列の周期を見つけること」に移したわけです。IBM：周期から因数への手順