Order Finding

In order to understand the application of the fourier transform to more applications, we'll first look at an algorithm called order finding.

This algorithm takes a periodic function as input and produces, as output, the period of that function. We'll talk a bit more about exactly what that means in a bit. But first let's go back to an old friend: modular arithmetic.

We first met modular (or clock) arithmetic in our article on fields. Doing arithmetic modulo $N$ essentially means only being concerned with the number's remainder when divided by $N$. So we get statements like the following:

This is saying that $13$ and $3$ are equal (or, more formally, congruent) mod $10$ as they both have the same remainder ($3$) when divided by $10$.

Order finding, is concerned with this equation:

Specifically, we will choose some value of $x$ and $N$ and ask: what is $r$? Put more plainly, this is: how many times do I have to multiply $x$ by itself before it gets back to $1$ modulo $N$?

This is a very important question in number theory. We won't dwell too much on all the interesting details, but it is important to note that for some $x$ and $N$ there is no such $r$. For example, if $x=2$ and $N = 8$, no matter how many times we multiply $2$ by itself, it will never get to $1$. This is fairly easy to see since multiplying by $2$ and taking a remainder when divided by $8$ will always give us an even number, whereas $1$ is odd.

It turns out, that $r$ only exists if $x$ and $N$ are co-prime. That is, they share no common factors.

One example would be when $x=5$ and $N = 21$, $r = 6$. This is because:

Exercise

Exercise

We call this value $r$ the order. Generally, computing the order is really difficult. At least for classical computers. We'll now apply the quantum fourier transform in order to solve it more easily using a quantum computer.

Like a lot of quantum algorithms, lets start by introducing an oracle. Our oracle will be the following:

It's important to note here that the 2 kets represent multiple quantum bits as just having single bit numbers wouldn't be very useful. We'll deliberately leave these two keys separate during our calculations and refer to them as the first/second register.

If we start in a state where all our qubits are $\ket{0}$ and then we apply a Hadamard gate to all the qubits in the first register we get:

Where $n$ is the number of qubits in the first register.

Applying our oracle now gives us:

We can then measure the second register. This will produce some value $f_0$ such that $f_0 \equiv a^{x_0}\ (\text{mod}\ N)$ for some $x_0$.

This now means the first register has dropped any states $\ket{j}$ such that $a^j \not\equiv f_0\ (\text{mod}\ N)$

So, where's $r$ going to come from in all this? For that, we'll jump back into a little bit of number theory.

Since we know $a^r \equiv 1\ (\text{mod}\ N)$ we have that for any numbers $x$ and $k$:

So, we know:

This means any value in the first register must now be of the form:$\ket{j+kr}$ for some $k$.

So our state now becomes:

Where $m$ is the number of remaining kets.

And now we apply the Quantum Fourier Transform:

That part in the brackets will prove crucial to us now.

If we expand the $\omega$ we get:

In case the text is getting too small, that fraction in the exponent is:

This is a geometric series and we can use the formula for the sum of a geometric series to get:

Now, if $k$ is a value very close to an integer multiple of $2^n/r$, i.e. $k \approx c2^n/r$ for some $c$, we can see the fraction in the exponent at the bottom is near to $1$ so the whole fraction gets very large. Otherwise the term is very small.

What this whole exercise essentially tells us is that the co-efficient for terms where $k$ is close to $c2^n/r$ will be very large, and the rest will be very small.

This means, upon measuring now the first register, we have a very high probability to measure a state of the form:

Great! That's all the messy quantum stuff out the way, now how do we get $r$ from this?

If we let our measurement be $y$ then we can simply divide by the known value $2^n$ to get:

Notice we say approximately here. This is because we can't gaurantee we measure an exact multiple, only that our measurement is very close.

Now, if $c$ and $r$ are not co-prime (i.e. they share a common factor), we can't extract $r$. e.g. if $c = 8$ and $r = 4$ then $y/2^n$ is $1/2$, so our $r$ value gets "destroyed" by the common factor cancelling. If we have this problem there's unfortunately no real way of knowing. We'll see later that if we fail in this way we will simply retry the quantum part of the algorithm.

Trying to extract $r$ from our$y/2^n$ value comes with another difficulty: We only used a finite number of bits. If $r$ is odd, then $1/r$ has an infinite decimal representation. So it's likely we may end up with an approximate value that is cutoff at some point.

Luckily, we know that $c$ and $r$ are integers, so our number must be rational. This means we can approximate $r$ with the process of continued fractions.

Continued fractions provides a way to develop a sequence of fractions providing better and better approximations to a given number. This also helps because we know we didn't necessarily measure an exact multiple of $2^n/r$.

The continued fraction for a number $q$ is:

Where the sequence of $a_n$ provides better and better approximations for $q$.

For example, if $q = 1.6$ we can find it's continued fraction with the following method:

Subbing each of those statements into the one above we have:

So our sequence is $a_0 = 1,\ a_1 = 1,\ a_2 = 1,\ a_3 = 2$.

Our approximations $p_n$ are then:

So, continued fractions gives us a list of continuing better approximations for our rational fraction. We can simply read off the denominator of any of them to get a candidate value for $r$. So our three candidate $r$ values in this example are: $1$, $2$ and $5$.

How do we check a candidate value? Just sub it into our original equation! $x^r\ \text{mod}\ N$ can be easily computed and checked by a classical computer. If it equals $1$ we are done. If it doesn't, we simply move on to our next candidate value.

If all of our candidate values fail, it means either $c$ and $r$ were not co-prime or our continued fractions approximation was unnsuccesful. In this scenario we just try again.

Now at this point, you're probably confused about this "trying again". Trying again, is not something we do in classical algorithms, but it can still be shown that doing this produces the correct answer quicker than any classical algorithm on average.

In fact, this algorithm actually performs better with bigger numbers! More qubits, produces more "sharp" spikes in the co-efficient of the $\ket{c2^n/r}$ states and also gives us a closer approximation for the continued fraction process. So whereas a classical algorithm would have to work harder for larger values of $x$ and $N$ a quantum computer actually gets more accurate making the speedup even more noticeable!

Let's quickly review the steps we went through:

1. Prepare two registers: $\ket{0}\ket{0}$
2. Hadamard gate all the qubits in the first register
3. Apply the oracle $U\ket{x}\ket{0} = \ket{x}\ket{a^x\ \text{mod}\ N}$
4. Measure the second register
5. Apply the Quantum Fourier Transform to the first register
6. Measure the first register
7. Use continued fractions on the measured value to approximate some candidate values for $r$
8. If no candidate values work, start again from step 1

We've skipped over a few details, such as how many qubits we should use and what the probability of success actually is but it's enough for now.

In the next article we'll use what we've learned to factor prime numbers!