19/02/26 22:15:55.38 vjaNCGJ/.net
量子コンピュータ - Wikipedia
ショアのアルゴリズム
ショアのアルゴリズムとは、素因数分解問題を高速に解くことができるアルゴリズムのことである。
古典コンピュータでは準指数時間で解くアルゴリズムしか知られていない。
1994年にピーター・ショアによって発見された。ショアは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。
2001年12月にIBMアルマデン研究所にて7qubitの量子コンピュータで15の素因数分解に成功した（Nature, 12月20日発行号）。
ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることによる。
また、アルゴリズム全体は確率的 (BQP) であり、正しい答えが得られるまで、何度も試行する。
手順の概略は以下の2つ。
全ての x に対して、均等な確率となるように初期化する。
そして、それを ax mod N のみ確率を持ち、それらは均等になるように変換する。
ax mod N は周期 r を持つ。この周期が求める位数である。
従って、1で得られた結果を離散フーリエ変換する。
すると、周波数 1/r のところの確率が大きくなるので、観測すると、高い確率で r が得られる。
失敗した場合は、成功するまで繰り返す。