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

/量子コンピュータ

ショアのアルゴリズム

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

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

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

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

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

具体例

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

  1. $15$ と約数を持たない整数 $x=7$ とする。
  2. 位数 $r$ を計算すると $r=4$ となる。
    $$7^4\bmod{15}=2401\bmod{15}=1$$
  3. 位数 $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$$
  4. これより $15=5\times3$ が求められる。

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

 

位数計算とは
量子コンピュータ、通常のコンピュータでは計算量的に難しい問題、量子アルゴリズム、量子回路、逆量子フーリエ変換
ユークリッド互除法とは
2つの正数の最大公約数を求めるアルゴリズム、拡張ユークリッド互除法、2つの正数と最大公約数の間の関係式
物理学
力学、連続体力学、電磁気学、波動・光学、相対論、熱力学、高校理科
散策路TOP
古典物理、量子力学、物性論、数学、応用数学、力学、電磁気学、相対論、熱・統計力学、解析学、代数学、幾何学、統計分析、情報

 

タイトルとURLをコピーしました