第42話 Shor（ショア）のアルゴリズム

これまでの話
第1話 量子の夜明け
...
第36話 量子ビット(ビットについて)
第37話 量子ビット(量子状態をコンピュータに使う)
第38話 量子ビット(N個のビット（N量子ビット）を構成する)
第39話 量子計算と基本量子ゲート
第40話 量子フーリエ変換と量子ゲート
第41話 量子計算とRSA暗号と素因数分解

を素因数分解する。ｘ< nで次式を満たすnと互いに素なxとrを探す。

このときrは周期で

このとき次式とnの最大公約数を求めるとnの因数となる。

Peter Shorの示した素因数分解のアルゴリズムはこれを量子計算することで効率的に行える事を示しました。実際に非常に効率的なアルゴリズムだったため量子コンピュータの研究開発に与えた影響は非常に大きいといえます。

このアルゴリズムを簡単な例を使って実際に確かめてみましょう。
n=15
x=2の例

x=7の場合
1,7,4,13,1,7,4,13,...　この場合は周期は４なのでOK

x=8の場合
1,8,4,2,1,8,4,2,... この場合は周期は４なのでOK

n=2007の場合x=40で1,40,1600,1783,1075,853,...周期は6です。

以上で見たように特に量子計算を行わなくても普通のアルゴリズムとしても使える事が分かります。しかし、実際には周期ｒを求めるのは大きな数ではやはり不可能に近い計算時間を必要としてしまいます。
Shorはこの周期ｒを求める部分を巧妙な方法で量子計算するアルゴリズムを発見したのです。そのアルゴリズムは見事と言うしかありません。

次回からはその妙技をじっくり見ていきたいと思います。