Due Wednesday November 16th, 2022

  1. I have posted some quantum-review questions on the “Goals” page (with solutions).
  2. Demonstrate the classical part of Shor’s algorithm using Sage, as follows:
      1. Choose N = 33463.
      2. Let a be your favourite random integer between 1 and N-1.
      3. 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.
      4. 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).
  3. 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$.
      1. For what values of $(x,y)$ do you have $f(x,y)=1$?
      2. For what values of $(x,y)$ do you have $f(x,y) = g$?
      3. Show that the function $f$ is constant on any line $L_K$ given by $y= ax + K$ for any constant $K$.
      4. 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)$.
      5. 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.