HW6 - Problem 4

Problem 4: Shor’s Algorithm Example

Consider the Period Finding algorithm for the function \(f : \{0, \ldots, N - 1\} \rightarrow \{0, \ldots, M - 1\}\), where \(f_x(s) = x^s \text{ mod } M\).

In this problem, we will use Shor’s algorithm to factor \(M = 817\) and \(N = 2^{20}\). Make sure you have the pseudocode in the notes for both Shor’s algorithm and period finding ready, as I will be referring to line numbers in those for the problems.

  1. Suppose that we sampled \(x = 357\) in step 1 of Shor’s algorithm. Explicitly write out what the function is that we pass to the period finding subroutine.
  2. (Period Finding) What is the period \(r\) of the function you wrote in the previous problem? You might want to write a quick Python script or notebook to find this. We will use this to guide the analysis, but in practice we don’t know what this is and discover it as the output of the process.
  3. (Period Finding) Suppose that we measure \(\ket{264}\) in the second register (step 4 of period finding pseudocode). Use what you know about the period \(r\) from the previous problem to determine what the state of the first register is after this measurement. It should be in a form

\(\frac{1}{\sqrt{s}}\sum_{j=0}^{s-1} \ket{jr + l}\)

but you should write the terms explicitly instead of using summation notation. 4. (Period Finding) In the next step, we apply the QFT in the first register and measure it in the standard basis. Suppose that the measurement outcome here was \(\left|141474\right>\). What is the fraction we are trying to approximate? Write down its continued fraction approximation. You may (should) use tools like wolframalpha.com.

You can type “continued fraction a/b” in the prompt to receive the approximation in a linear form \([a; r_1, r_2, r_3,...]\) which means

\(\frac{a}{r_1-\frac{1}{r_2-\frac{1}{r_3 ...}} }.\)

The nice thing about Wolfram is that you can also evaluate an approximation given in a linear form by typing “evaluate continued fraction \([a; r_1, r_2, r_3,...]\)”. You can then try different approximations by only considering the first \(k\) \(r_i\) terms. The denominators in these approximations are the \(Q_0<Q_1<\cdots\) in the notes. One of these should be the period of \(f\). Which one is it? 5. We now return to Shor’s algorithm, using the value of \(r\) we found from period finding. Evaluate \(\gcd(x^{r/2}, 817)\) and \(\gcd(x^{r/2},817)\) to find the factors of \(M\). What were they?