Now that we understand what the quantum Fourier transform (QFT) does, and we know what the period of a function is, we can talk about how the QFT is used to execute the period finding function.

You probably have a pretty good idea how this works already. In the last phase of the discussion of the QFT, we saw that the QFT operating on a superposition state behaves in striking ways. If the input superposition is something like (|0rangle+|4rangle) then some of the terms cancel, and the output is (|0rangle+|2rangle+|4rangle+|6rangle).

Note that all of the values in the output superposition are multiples of two. Two happens to be the number of terms in our input superposition! Is that significant?

Turns out that it is. We can set up our algorithm so that the number of terms in that output superposition is the period of the function.

Let’s walk through an example. Can we factor the number (N = 21) using Shor’s algorithm? Consider the sequence (2^i), for some long series of numbers:

(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)

(Instead of 2, we could have picked almost any number greater than one and less than the number we are trying to factor, but 2 makes a nice, simple case. Sometimes by accident we choose a number that doesn’t work well, but that should be rare.)

We can see that every six steps we come back to 1. The period of this function is six. If we write out the sequence, we get (1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, 2, 4, 8, 16, 11, 1, …).

Let’s pair each input number with its output number:

and on and on. Now, let’s sort those lines by the output number:

In Shor’s algorithm, the modular exponentiation step does exactly this. It groups input values that all have the same output value: give me a list of all of the values for (x) for which (2^x bmod 21) equals the same value.

Before we run the QFT, we measure some of our qubits (just the ones holding the output value), which causes the quantum state to partially collapse. This measurement causes one of the output values to be picked at random. If the output value we find is 1, for example, we would have left a superposition like this:

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

If instead we found the output value 11, we would have the list

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

In any case, we have a superposition with the period six.

If we have nine qubits, there are (2^9 = 512) basis states, 0 through 511, and we are creating interference across them. Since we have divided them up into 6 roughly equal sets, there are about (512/6 approx 85) members of each set. This number shows up in the QFT of our superposition

where the peaks (corresponding to high probability of being measured) appear at 0, 85, 171, 256, 341, and 427. As you can see in the picture, the six peaks aren’t all the same size, but they are all between 11% and 17%, so very, very roughly we can say that there is a similar probability of getting each of those results when we measure our register at the end of the quantum part of the computation.

Once we have the result, we then take that and turn it into the period. If we measure and find, for example, the value 85, then we use the value (512 / 85 approx 6). The procedure for finding the period is actually a little more complicated than this, but we don’t need to go into the details. That complexity is needed when we get one of the numbers larger than 85, which will happen most of the time. Occassionally, we find the number 0 when we measure, which we can’t use, so we rerun the quantum part of the algorithm and hope for a different result the next time, which probability suggests we are likely to get.

The Final Step: Euclid

Earlier, we saw how Euclid’s algorithm can be used to find the greatest common denominator (gcd) of two integers. Now, we’re going to need it.

Take the period we just found (call it (r); in this case, (r = 6)), and use the number we picked to exponentiate (call it (a); in this case, (a = 2)). Calculate the numbers (a^{(r/2)}+1 = 2^{(6/2)}+1=2^3+1 = 9) and (a^{(r/2)}-1 = 2^3-1 = 7).

Finally, take each of those two numbers and our number we’re trying to factor ((N = 21)), and

use Euclid’s algorithm to find the gcd:

gcd(9,21) = 3

gcd(7,21) = 7

and of course (21 = 7 times 3), so we have found the two factors of our number!

量子周期の発見

量子フーリエ変換（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つの数字を見つけました！