周期 \(r\) を求める

周期 \(r\) を求めるには、パターンを取り出すツールである QFT を使います。 たとえば \(N = 15\), \(a = 2\) の場合、後で実際に実行して確認しますが、\(2^x\,mod(15)\) の値を持つ状態ベクトルに QFT を適用し測定すると、次のような確率のピークがいくつか得られます。

QFT で得られる確率のピークは、周期 \(r\) のヒントを与えるものです。 ピークの数はちょうど周期 \(r = 4\) と同じになり、0 から始まって等間隔に並びます。

これを測定すると 0, 4, 8, 12 のうち 1 つだけがランダムに手に入るので、測定結果からは直接周期 \(r\) は得られないことに注意してください。 しかし、これらは等間隔であること、また x の範囲は 0 〜 15 であることをうまく使うと、周期 \(r\) の候補が計算から推定できます。

この \(r\) の候補を出すアルゴリズムを連分数アルゴリズムと呼びます。 詳細は省きますが興味のある読者は、Qiskit チュートリアル「ショアのアルゴリズム」を参照してください。https://qiskit.org/textbook/ja/ch-algorithms/shor.html これは古典コンピュータで計算でき、\(N = 15\), \(a = 2\) の場合には \(r\) の候補として 2 と 4 が得られます。 測定値 4、8、12 を 16 で割って既約分数にすると、分母はそれぞれ 4、2、4 になります。 測定値 0 からは有用な候補が得られないので、測定をやり直します。

あとは \(r = 2, 4\) それぞれの候補について \(gcd(N, a^{r/2} + 1)\) と \(gcd(N, a^{r/2} - 1)\) を計算して、結果が 1 より大きく \(N = 15\) より小さい非自明な因数かチェックします。非自明な因数が得られたら、\(N\) をその因数で割ってもう一つの因数を求めます。これらは古典コンピュータで簡単にでき、 \(r = 4\) の場合因数 3 と 5 がみつかるので、計算は終了です。