動かして学ぶ量子コンピュータプログラミング ―シミュレータとサンプルコードで理解する基本アルゴリズム

12.2

 ショアのアルゴリズムが行うこと

233

// classical part



var factors = ShorLogic(N, repeat_period, coprime);

return factors;

}

function ShorLogic(N, repeat_period, coprime) {



// Given the repeat period, find the actual factors

var ar2 = Math.pow(coprime, repeat_period / 2.0);

var factor1 = gcd(N, ar2 - 1);

var factor2 = gcd(N, ar2 + 1);

return [factor1, factor2];

}

前述のように、

QPU

は作業の一部のみを行っています。

Shor()

関数は、他の

2

つの関数を呼び出

します。

1

番目の関数

ShorQPU()

は、

QPU

（またはそのシミュレーション）を巧みに利用して、反復周

期を見つけます。一方、次の関数

ShorLogic()

で行われる残りの作業は、

CPU

上で動作する従来型

のソフトウェアで実行されます。これらの関数それぞれについては、次のセクションで詳しく説明しま

す。

この例で用いる

ShorLogic()

の実装は、一例を示すためだけのものです。説明はより簡単

ですが、非常に大きな数の場合は計算時間がかかります。本格的なショアのアルゴリ ...