Period Finding with Quantum Mechanics

We have seen that if we can quickly solve the period finding algorithm, then we can factor.

We have also seen that if we have a unitary matrix, we can find the phase of the eigenvalues.

Now we will find a unitary matrix $U_{x,N}$ whose phase of their eigenvalues $\theta = s/r$ where $s$ is an integer and $r$ is the period we are after. In addition we we will see how to quickly extract $r$ from this decimal.

In future pages we will

Show that there exists a quantum circuit which quickly applies $U_{x,N}$ to a state
Show that there exists a quantum circuit which quickly applies a controlled version of $U_{x,N}$ to a state
Implement controlled-$U_{x,N}$ as an atomic gate in our quantum simulator.
Put everything together for Shor's algorithm.

Let's first remind ourselves what the period finding pieces we are building needs to do:

Period finding problem: Given $x$ and $N$, find the $r$ such that $x^r \textrm{ (mod N) } \equiv 1 \textrm{ (mod N) }$

Our next step is going to be finding that there is a unitary operator $U_{x,N}$ which depends on $x$ and $N$ which has the property that its eigenvalues (essentially) give us $r$.

We are going to describe a unitary operator $U_{x,N}$ which depends on $x$ and $N$. Remember, one way I can describe what a unitary operator does is to tell you what it does on every basis element.

We will assume we are working with a number of qubits of size $n=\lceil log N \rceil$

$U |j\rangle \rightarrow |(j x) \textrm{ (mod N) } \rangle \textrm{ if } j<N$
$U |j\rangle \rightarrow |j \rangle \textrm{ if } j \geq N$ (this is just to define it all the way up to $n$)

Notice that this is unitary.

	Grading
	Write code that generates this unitary matrix for an arbitrary co-prime (x,N). (To test this you can get such an (x,N) from your previous code to run Shor's algorithm).

Because the matrix is unitary, the eigenvalues of the matrix are just phases (convince yourself this has to be true of any unitary matrix). We are now going to notice something additionally interesting about these phases. Take your function which generates this matrix and put it into your classical Shor's algorithm code where you choose $x$ and $N.$
Define the phase $\theta$ such that $\lambda = \exp[2\pi i \theta]$.

Now, run your Shor's algorithm code and find the vector $e$ of all the phase of the eigenvalues (there should be $n$ of them). If you compute $e*r$, you should notice that you generate integers. This means that all of the eigenvalues are of the form $s/r$ for some integer $s.$

	Grading
	Verify that this is what you get. Paste your eigenvalues before and after you multiply by $r$ as well as your value of $r$ into your document.

(Think about why this is?)

What this means is that if you could find the phase (we will see soon how to use a quantum computer to do this) and if you could figure out what the $s$ and $r$ was then you could find the period $r$ you want.

There is a general (fast classical) algorithm which takes a decimal number $d$ and finds $s$ and $r$. This is called the continuing fractions algorithm.
You can do this in python by doing

from fractions import Fraction
Fraction.fraction(myDecimal).limit_denominator(the_largest_possible_value_of_r)

Notice, that there are two failure modes in this approach:

You might have a phase of 0. If you have a phase of 0, there's no way to pull out $r$ since $s=0$.
Suppose you were looking for $s/r=5/10$. The continuing fraction algorithm will give you $s/r=1/2$ which is true but not very helpful because the period isn't two. Luckily this doesn't happen because most $s$ and $r$ are co-prime.

If you hit one of these failure modes just start over with a new $x$. These failure modes don't happen too often.

	Grading
	Show that you can find the period $r$ given a random eigenvalue from the matrix $U_{x,N}$.

Now, let's go ahead and modify your factoring algorithm so that instead of doing period finding the old way, it builds the matrix $U$ and then picks a random eigenvalue, runs the continuing fraction algorithm on the eigenvalue and generates the period.

	Grading
	Show that this works by factoring some numbers.