## Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.
3.16

# Quantum Period Finding

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 $$|0\rangle+|4\rangle$$ then some of the terms cancel, and the output is $$|0\rangle+|2\rangle+|4\rangle+|6\rangle$$.

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:

input output   input output
0 1   13 2
1 2   14 4
2 4   15 8
3 8   16 16
4 16   17 11
5 11   18 1
6 1   19 2
7 2   20 4
8 4   21 8
9 8   22 16
10 16   23 11
11 11   24 1
12 1

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

input output   input output
0 1   3 8
6 1   9 8
12 1   15 8
18 1   21 8
24 1   4 16
1 2   10 16
7 2   16 16
13 2   22 16
19 2   5 11
2 4   11 11
8 4   17 11
14 4   23 11
20 4

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:

$|0\rangle+|6\rangle+|12\rangle+|18\rangle+|24\rangle ...$

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

$|5\rangle+|11\rangle+|17\rangle+|23\rangle+|29\rangle ...$

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が動作するのを見て来ました。もし入力される重ね合わせ状態が $$\vert0\rangle+\vert4\rangle$$のようなものだと、いくつかの項がキャンセルされて出力は$$\\vert0\rangle+\vert2\rangle+\vert4\rangle+\vert6\rangle$$になります。

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

$$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$$

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

input output   input output
0 1   13 2
1 2   14 4
2 4   15 8
3 8   16 16
4 16   17 11
5 11   18 1
6 1   19 2
7 2   20 4
8 4   21 8
9 8   22 16
10 16   23 11
11 11   24 1
12 1

input output   input output
0 1   3 8
6 1   9 8
12 1   15 8
18 1   21 8
24 1   4 16
1 2   10 16
7 2   16 16
13 2   22 16
19 2   5 11
2 4   11 11
8 4   17 11
14 4   23 11
20 4

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

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

$|0\rangle+|6\rangle+|12\rangle+|18\rangle+|24\rangle ...$

$|5\rangle+|11\rangle+|17\rangle+|23\rangle+|29\rangle ...$

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

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

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

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

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

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

gcd(9,21) = 3

gcd(7,21) = 7

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