I have posted some quantum-review questions on the “Goals” page (with solutions).

Demonstrate the classical part of Shor’s algorithm using Sage, as follows:

Choose N = 33463.

Let a be your favourite random integer between 1 and N-1.

Define R = IntegerModRing(N) and alpha = R(a). The Sage command alpha.multiplicative_order() will play the role of the quantum computer; it outputs the multiplicative order of alpha.

Use the result to factor N, in the manner of Shor’s algorithm, as described in class. If it doesn’t work, try another random a (as you would in Shor’s algorithm).

This exercise gets you closer to computing a discrete logarithm on a quantum computer. Suppose $h = g^a$ for some unknown $a$. Consider the function $f: \mathbb{Z}/(p-1)\mathbb{Z} \times \mathbb{Z}/(p-1)\mathbb{Z} \rightarrow \mathbb{Z}/p\mathbb{Z}$ given by $(x,y) \mapsto h^{-x} g^y \pmod p$.

For what values of $(x,y)$ do you have $f(x,y)=1$?

For what values of $(x,y)$ do you have $f(x,y) = g$?

Show that the function $f$ is constant on any line $L_K$ given by $y= ax + K$ for any constant $K$.

Show that $f$ is `periodic’ in the sense that it repeats when we add any $(z,az)$ to the input values. In other words, $f(x,y) = f(x+z,y+az)$.

Suppose you somehow discover that $f(x_1,y_1) = f(x_2,y_2)$ for different input pairs. Explain how you can compute $a$ from this.