周期パターンの読み出し

あとは状態ベクトルに展開された \(2^x mod(15)\) の周期パターンを QFT で読み出すだけです。 ここで QFT をなんとなく回路全体に適用したくなりますが、それは間違いです。 QFT で取り出したいパターンがどのように状態ベクトル中に埋め込まれているか、もう一度確認してみましょう。

ここで取り出したいのは、確率がゼロではない振幅が 3 つおきに登場しているというパターンです。 この「3 つおき」は \(x\) の値として現れる情報です。 なので QFT は次のように \(x\) を表す量子ビットにだけにかける必要があります。

最後の測定で 0, 4, 8, 12 のいずれかが求まることを確認してください。 これを連分数アルゴリズムにかければ、\(r\) の候補として 2 と 4 が得られます。 測定値 4、8、12 を 16 で割って既約分数にすると、分母はそれぞれ 4、2、4 になります。 測定値 0 からは有用な候補が得られないので、測定をやり直します。 そして gcd を計算して、結果が 1 より大きく \(N = 15\) より小さい非自明な因数かチェックします。非自明な因数が得られたら、\(N\) をその因数で割ってもう一つの因数を求めます。 \(r = 4\) の場合因数 3 と 5 がみつかります。 長い道程でしたが、\(15 = 3 \times 5\) の因数分解を実行するショアのアルゴリズムができました!