ショアのアルゴリズム

現在の量子コンピューターには、量子ノイズや、量子力学的干渉の破壊といった課題が存在する。しかし、それらの課題を克服し、ある程度の量子ビット数の量子コンピューターを、操作することができるようになったとすると、RSA暗号、ディフィー・ヘルマン鍵共有、楕円曲線ディフィー・ヘルマン鍵共有などの公開鍵暗号の解読ができてしまうと考えられている^[6]。なぜなら、例えば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の素因数である^[7]。

例えば、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」が素因数である。