Quantum Period Finding／量子周期の発見

量子フーリエ変換（QFT）の働きを理解し、関数の周期を知ったので、QFTを使用して周期探知関数を実行する方法について話します。

どのように周期関数が機能しているのか、既に予想が付いているかもしれません。 QFTの議論の最後に、重ね合わせ状態でQFTが動作するのを見て来ました。もし入力される重ね合わせ状態が (vert0rangle+vert4rangle)のようなものだと、いくつかの項がキャンセルされて出力は(vert0rangle+vert2rangle+vert4rangle+vert6rangle)になります。

出力される重ね合わせの値は全て2の倍数であることに注意してください。 2つは入力された重ね合わせの項の数になります！ この事実は重要です。

これによって出力される重ね合わせ状態の項の数が関数の周期になるようにアルゴリズムを設定することができます。

例を見てみましょう。私たちはショアのアルゴリズムを使って(N=21)を因数分解できるでしょうか。2の(i)乗 に対して大きい数で考えてみましょう。

(2^0 = 1 bmod 21 = 1)
(2^1 = 2 bmod 21 = 2)
(2^2 = 4 bmod 21 = 4)
(2^3 = 8 bmod 21 = 8)
(2^4 = 16 bmod 21 = 16)
(2^5 = 32 bmod 21 = 11)
(2^6 = 64 bmod 21 = 1)
(2^7 = 128 bmod 21 = 2)
(vdots)

因数分解する数より小さく1より大きい数字のいずれかを、2の代わりに選ぶことができます。２は単純でわかりやすいケースです。誤ってうまくいかない数を選択することもありますが、それは稀です。)

6ステップごとに１に戻ることがわかります。そのため、この関数の周期は６です。順番に書きだすと(1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, …)となります。

各入力番号とその出力番号をペアにしましょう:

続いて、これらの行を出力番号でソートしましょう:

Shorのアルゴリズムでは、冪乗余のステップでこれを行います。同じ出力値を持つ全ての入力値をグループ化します。つまり(2^x bmod 21)が等しいすべての(x)の値のリストを求めます。

QFTを実行する前に、いくつかの量子ビット（出力値を保持する量子ビット）を測定し、量子状態を部分的に崩壊させます。 この測定により、出力値の1つがランダムに選択されます。 たとえば、見つかった出力値が1の場合、次のように重ねて表示されます。

[|0rangle+|6rangle+|12rangle+|18rangle+|24rangle …]

出力値11が見つかった場合は、以下のリストを得ます。

[|5rangle+|11rangle+|17rangle+|23rangle+|29rangle …]

いずれにせよ、私達は6周期の重ね合わせを得ます。

もし9量子ビットがある場合、(2^9 = 512)の状態、つまり0から511があり、それらの間に干渉が生じています。それらを6つのほぼ数の等しいグループに分けたため、各グループの中には(512/6 approx 85)個あります。この数は、重ね合わせのQFTに現れます。

(測定される可能性の高い確率に対応する)ピークは、0, 85, 171, 256, 341,427に現れます。画像のように、6つのピークはすべて同じサイズではありませんが、すべて 11％から17％の間にあるので、大まかに言って、計算の量子部分の終わりにレジスタを測定すると、それぞれの結果を得る確率はおおよそ同じです。

結果が得られたら、それを取って周期に変えます。 たとえば、値85を測定して見つけると、(512 / 85 approx 6)の値が得られます。 周期を見つける手続きは実際にはこれより複雑ですが、ここでは触れません。

その複雑さは、私たちが85よりも大きい数を得るときに必要とされます。これはほとんどの場合起こります。 時には、我々が使用することができない測定時に数字0を見つけるので、アルゴリズムの量子部分を再実行し、次回に別の結果が得られることを期待しています。

最後のステップ：ユークリッド

先ほど、ユークリッドのアルゴリズムを使って、2つの整数の最大公約数（gcd）を見つける方法を見てきました。 今からそれを利用します。

見つかった周期((r)と呼ぶ、この場合は(r=6))をとり、これを累乗に使用します（(α)と呼ぶ、この場合は(α=2))。

(a^{(r/2)}+1 = 2^{(6/2)}+1=2^3+1 = 9) and (a^{(r/2)}-1 = 2^3-1 = 7)

最後に、これらの2つの数字と因数分解しようとしている数字((N=21)) にユークリッドのアルゴリズムを使い、

gcd(9,21) = 3

gcd(7,21) = 7

(21 = 7 times 3)で、2つの数字を見つけました！