ショアのアルゴリズムとは

ショアのアルゴリズム

ショアのアルゴリズムとは、従来のコンピュータでは非現実なほど時間が掛かってしまう因数分解を、量子コンピュータの仕組みを使って高速に計算するためのアルゴリズムです。

因数分解したい整数を $M$ とすると、因数分解の手順は以下になります。

$M$ と約数を持たない整数 $x$（$x\lt M$）を適当に決める。
$M$ と $x$ の位数 $r$ を計算する。
$$x^r\bmod{M}=1$$
$r$ が偶数であれば、$\mathrm{gcd}(x^{r/2}-1,M)$ と $\mathrm{gcd}(x^{r/2}+1,M)$ を計算する。
※$\mathrm{gcd}$ は最大公約数を表す。
これらのうち１つが $M$ の因数であれば終了。そうでなければⅠに戻る。

このような因数分解の手順は従来から知られていましたが、その中にⅢの位数計算のような非常に時間を要する計算が含まれており、それに対して有効な手法が見出せていませんでした。

1995年、ショアは量子アルゴリズム（ショアのアルゴリズム）を使って、Ⅱの位数計算が高速に行えることを示しました。尚、Ⅲの最大公約数を求める手法は、ユークリッド互除法が知られています。

実際にショアが計算した $M=15$ の場合を例にとると、

$15$ と約数を持たない整数 $x=7$ とする。
位数 $r$ を計算すると $r=4$ となる。
$$7^4\bmod{15}=2401\bmod{15}=1$$
位数 $4$ は偶数なので最大公約数を計算すると、
$$\mathrm{gcd}(7^{4/2}-1,15)=\mathrm{gcd}(48,15)=3$$$$\mathrm{gcd}(7^{4/2}+1,15)=\mathrm{gcd}(50,15)=5$$
これより $15=5\times3$ が求められる。

これは簡単な例なので暗算でも求められますが、Ⅱの位相計算は量子アルゴリズム（ショアのアルゴリズム）を使って解き、Ⅲの最大公約数はユークリッド互除法を使って解きます。