Shor’s Algorithm

We are now going to work up to implementing Shor’s algorithm to factor numbers.

These three points will correspond to the next three pages you work on. This summarizes what you will be doing and will be useful reference later but the details won’t make sense yet.

Classical Scaffolding: First, we are going to implement the classical scaffolding for Shor’s algorithm.

There will be a slow step in this process. In particular, you are going to need to find a number \(r\) such that \( x^r = 1\mod N\).

In the classical scaffolding you will implement this slow part slowly. In particular you will write a python function that just check each \(r\) and returns the correct one.

Quantum Matrix: Second, you are going to replace the slow python function for finding \(r\) (with another slow function). This is an intermediate step and involves “quantum” but no quantum circuits or computing yet. To find \(r\), you will first build the unitary matrix \(U\) which implements the gate \(xy \mod N\). Then you will compute the eigenvalues (np.linalg.eig) of this matrix, determine their phase (np.angle(e)/(2*np.pi)) and use a continuing fraction algorithm (Fraction) to extract the \(r\) from \(s/r\).

Quantum Circuit: Finally, you are going to replace the function which computes \(r\) from the phase of the eigenvalues of the \(xy \mod N\) matrix by a quantum circuit which outputs the phase of the eigenvalues of the \(xy \mod N\) matrix. This function will be slow but only because you are emulating a quantum computer on a classical computer. If you actually had a real quantum computer it would be quick.