Shor's Algorithm

Given a number , find a nontrivial factor.

We try to use Periodicity Determination on a function finding some smallest period .
If is even, we find that

As is the smallest period, it cannot be that .
Now may give us a nontrivial factor of .
This is likely to succeed.

Finding the period

Let be the smallest integer such that .
Pick a random integer .
We try to implement Periodicity Determination of on a whole domain .
Start from state .
Apply on the first registers:

Apply the quantum oracle for :

We measure the last register leaving the state in:

for some
Apply to get

Now we need to look closely into
in particular, we want to be close to an integer, say
In that case, .
Note that there is a unique integer such that

The probability of measuring such turns out to be at least .
We do have candidates, so the probability of measuring for some is at least .

Given some we need to extract from it.
We find the Continued Fraction of .
Checking it’s convergents we look for such that:

and .
Having found one such , we reduce it to lowest terms, and pray that AND is even.
We can easily check this.
If we are lucky, we can apply the reasoning at the start of this page (otherwise, repeat the whole process with a different )