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:

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

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!