 を素因数分解する。ｘ< 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はこの周期ｒを求める部分を巧妙な方法で量子計算するアルゴリズムを発見したのです。そのアルゴリズムは見事と言うしかありません。 次回からはその妙技をじっくり見ていきたいと思います。
|
この記事に
そうですね。Shorのアルゴリズムがなかったら、量子コンピュータの研究は盛んにならなかったでしょう。量子誤り訂正が可能であることを最初に示したのもShorでした。彼がこの分野への貢献は本当に大きかったです。
[ entangled74 ]
2007/4/28(土) 午前 1:15
返信する私なりに理解したつもりですがこのアルゴリズムには久しぶりに感動しましたね。研究者の方はどんな感想をもたれたんでしょうか？ 量子誤り訂正も気になってまして勉強して見ようと思っています。保護ビットを追加する辺りまでは見てるんですがその先はちょっと難しい気がします。entangled74さんが以前書かれていますね。参考にさせていただきます
2007/4/28(土) 午前 1:31
返信する量子誤り訂正について以前少し書きましたが、途中やる気をなくして、今は不完全な状態のままですね。重要なことはほとんど書いていません。この解説論文はわかりやすいので、おすすめします。http://arxiv.org/PS_cache/quant-ph/pdf/0602/0602157v1.pdf
[ entangled74 ]
2007/4/28(土) 午前 1:48
返信する