ショアのアルゴリズム

ショアのアルゴリズム（英: Shor's algorithm）は、1994年にアメリカの数学者ピーター・ショアによって考案された^[1][2][3][4]、素因数分解問題を高速に（多項式時間で）解くことができるアルゴリズムのことである。いまのところ古典コンピュータでは非現実的な時間（分解したい整数の桁数についての準指数時間）で解くアルゴリズムしか知られていない^[5]。一方で、実用的に使用されるような素因数分解が解けるようになるには、将来的にさらなる量子ビットが必要である^[6]。ショアは本件で、ネヴァンリンナ賞とゲーデル賞を受賞した。また、2001年12月にIBMアルマデン研究所にて7量子ビットの量子コンピュータで15 (= 3×5) の素因数分解に成功した^[7]。

実現可能性とその影響

現在の量子コンピューターには、量子ノイズや、量子力学的干渉の破壊といった課題が存在する。しかし、それらの課題を克服し、ある程度の量子ビット数の量子コンピューターを、操作することができるようになったとすると、RSA暗号、ディフィー・ヘルマン鍵共有、楕円曲線ディフィー・ヘルマン鍵共有などの公開鍵暗号の解読ができてしまうと考えられている^[8]。なぜなら、例えばRSA暗号は、大きな素数同士の合成数を機械で素因数分解するのは、膨大な時間がかかり困難であるという推定のもとで基づいているからである。

アルゴリズムを少し変更することで離散対数問題（DLP, ElGamal暗号や楕円曲線暗号の安全性の根拠）も多項式時間で解くことができる。このアルゴリズムの基本的なアイデアを拡張したものが、可換隠れ部分群問題についての量子アルゴリズムである。現在は、これをさらに非可換隠れ部分群問題に拡張する研究が進展している。

アルゴリズム

ショアのアルゴリズムは、量子コンピュータが離散フーリエ変換を高速に実行できることを用いている。また、アルゴリズム全体は確率的 (BQP) であるので、正しい答えが得られるまで、何度も試行をする必要がある。

1. 素因数分解したいNと互いに素な整数aを用意する。
2. Nの二進数表記の桁数をLとし、位相推定の精度tは2L+1とする。
3. 第一レジスタにアダマールゲート操作を施し、第二レジスタに制御ユニタリゲートU_n,aを作用させる。ここで、U_n,aとは以下の計算過程集合である。U_n,a|α⟩=|αa mod N⟩と変換するようなaとNを引数とするユニタリ演算子U_n,aを考え、その固有値を取り出す。(量子位相推定)
4. 適切な位数rが見つかったら、p=gcd(a^r/2+1,N),q=gcd(a^r/2-1,N)がNの素因数である^[9]。

量子位相測定のサブルーチン

位数を求める具体例

例えば、N = 15, a = 7 とする。

7⁰ = 1 (mod 15)

7¹ = 7 (mod 15)

7² = 4 (mod 15)

7³ = 13 (mod 15)

7⁴ = 1 (mod 15)

7⁵ = 7 (mod 15)

7⁶ = 4 (mod 15)

7⁷ = 13 (mod 15)

7⁸ = 1 (mod 15)

7⁹ = 7 (mod 15)

⋮

1,7,4,13,1,7,4,13,1,7,…という周期 4 の数列が生成される。

よって、周期 r = min{x > 0|7^x = 1 (mod 15)} = 4

p = gcd(a^r/2+1,N) = gcd(7^4/2+1,15) = gcd( 50, 15) = 5

q = gcd(a^r/2-1,N) = gcd(7^4/2-1,15) = gcd( 48, 15) = 3

よって、最終的に得られる「5, 3」が素因数である。