インターネットで広く利用されている暗号系として代表されるものに
RSA 暗号系があります。この暗号系は、秘密鍵とよばれる数字の組みを知らない第
3 者が、暗号を解読することがきわめて困難であることが知られています。これは、RSA
暗号系が、整数論で知られている次の事実による暗号系であることによります。すなわち、大きな数の因数分解を多項式時間で効率的に解くことのできるアルゴリズムが、いまだ知られていないという事実です。
1994 年に Shor は、この因数分解を量子コンピュータで、きわめて効果
的に解けることを示しました。これにより、それまで理論的で抽象的なイメージの大きかった量
子コンピュータの有効性が明らかになるとともに、量子コンピュータの研究を大きく前進させる契機となりました。
Shor のアルゴリズムは、量子コンピュータによる計算部分と、古典的な計算による部分とに大別
されます。このシミュレータでおこなえるのは、量子コンピュータに依存した計算部分のみです。すなわち、以下に示す手順のステップ
1〜ステップ 4の部分のみのシミュレーションとなります。
Nを因数分解する Shor のアルゴリズムの手順は、次の通りです。
(準備)
をみたすqを選ぶ。Nと互いに素な整数Xをランダムに選ぶ。
(初期化)、(ステップ 1) 〜 (ステップ 4)、(測定) を繰り返す。
(初期化)
レジスタ 1 とレジスタ
2 を 0 に初期化します。
(注意)
量子ビットをいくつかまとめたものを、量子ビット列、もしくはレジスタ
(register) といいます。
(ステップ 1)
レジスタ 1 のすべての量
子ビットに 
ゲートを作用させます。このときのレジスタの状態は
で与えられます。
(ステップ 2)
レジスタ 1 を入力のパラメータとして
を計算します。これによりレジスタの状態は
となります。
(ステップ 3)
レジスタ 2 を測定します。このとき、レジスタ 2 の値がKになったとすると、レジスタ
1 とレジスタ 2 の値の組みは、 
とし、 
を集合Aの要素数とすると
で与えられます。
(ステップ 4)
レジスタ 1 の離散フーリエ変換 (DFT) を計算します。
離散フーリエ変換は
なる写像ですから、レジスタの値の組みは
で与えられます。
(測定)
レジスタ 1 を測定します。
レジスタ 1 を測定した結果が 
であるなら、このは、求めたい周期を
としたときの
の値の整数倍になっています。を連分数展開することにより、周期が決定されます。
(準備)、(ステップ 1) 〜 (ステップ 4)、(測定) を 
だけ繰り返すことにより正確な周期を決定することができます。
周期 が決定されたのであれば
N の因数は
を計算することにより得られます。
Shor のアルゴリズムを理解する上で、重要な部分は手順で示される
(測定) の部分です。アルゴリズムは、非常に高い確率で、求めたい周期
? を決定するために必要な情報を返しますが、まれに、望まない結果
を返します。これは、量子計算における測定が、確率的なものであることに起因しています。
量子コンピュータで効率的と考えられるアルゴリズムは、等確率で分布する状態ベクトルをもちいて、必要な計算を一度でおこなうことに特徴があると考えられます。しかし、測定により、どの状態が観測されるかは、まったく確率的です。いかに高い確率で、求めたい結果
を得られるようにアルゴリズムが設計されているかどうかは、そのアルゴリズムの優劣の評価に、きわめて大きな影響を与えます。
ここでは Shor のアルゴリズムの概要を述べたに過ぎません。正確な
Shor のアルゴリズムの理解と有効性の検証のためには、整数論などの知識を含めた広範囲な知識が必要となります。
詳しくは
Shor, W. Peter, "Polynomial-Time Algorithms for Prime Factorization
and Discrete
Logarithms on a Quantum Computer", Proceedings of the 35th
Annual Symposium
on Foundations of Computer Science, Santa Fe, NM, Nov. 20-22,
1994,
IEEE Computer Society Press, pp. 124-134 (quant-ph/9508027)
Williams, Colin P. and Clearwater, Scott. H., "Breaking Unbreakable
Codes", Chapter 6,
Explorations in Quantum Computing, 1998
などを参照して下さい。
