ショアの因数分解

周期パターンの読み出し

周期 r を決めるためのパターンを QFT で調べる

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

f(x) の値
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
x の値
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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

最後の測定で 0, 4, 8, 12 のいずれかが求まることを確認してください。 これを連分数アルゴリズムにかければ、\(r = 4, 8\) が得られます。 そして gcd を計算して実際に \(N = 15\) の約数として正しい 3, 5 が求まります。 長い道程でしたが、\(15 = 3 \times 5\) の因数分解を実行するショアのアルゴリズムができました!