Shor's algorithm: what to do after reading the QFT's result twice?

Question

I asked about how to identify the period looking at a Fourier transform plot. The answer seems to be to run the fourier transform multiple times getting multiple values associated to high probabilities described by the graph. So still using the same picture, suppose I read it twice and I got the values |5> and |11>. These are the highest spikes (after the first highest in |0>.) How would I figure out the period 12 out of 5 and 11? Can you show an example of the calculation?

An attempted solution. Reading Peter Shor's paper (on page 320), we find that his $q$ is $q=64$ here in our example. Shor is saying we can obtain a fraction $d/r$ in lowest terms (where $r = 12$ here) by rounding $c/q$ to the nearest fraction having a denominator smaller than $n=35$ here. Our possible $c$ here is $5$ and $11$.

Let's try that. After the QFT, we got $c = 5$ and we have $q = 64$. So we get $5/64 = 0.078125$ and we want to round that to the nearest fraction having a denominator smaller than $35$. For $5/64$, I find the continued fraction $[0,12,1,4]$. (I checked that $5/64 = 1/(12 + 1/(1 + 1/4))$, so that's correct.) Now, from this continued fraction (in list form) I get the following sequence of fractions: $1/4, 5/4, 64/5, 5/64$. (I'm not sure what I'm doing.) Perhaps $5$ is bad luck? But, no, trying the same thing with $11$ will also produce $11/64$. So even though I know how to compute the continued fraction algorithm, I don't know what to do with it. I'm gonna have to look at Hardy and Wright, Chapter X.

Answer 1

This is the continued fraction part of the algorithm, step 5 on Wikipedia. What you've measured is $y$ such that $\frac{yr}{Q}\approx c$, where $c$ is some unknown integer, $r$ is the hidden period (in this case 12), and $Q=64$ is the size of the QFT. This means that $\frac{y}{Q}\approx \frac{c}{r}$. For $y=5$, we have $\frac{5}{64}\approx \frac{1}{12}$, and for $y=11$, we have $\frac{11}{64}\approx \frac{2}{12}$. So that's the relation between the measured values and the period.

How do we actually find the period from those values, though (since we don't know $c$ or $r$)? With continued fractions. A continued fraction for a number $x$ is defined recursively, with $a_0=x$, then with $b_n=\lfloor a_n\rfloor$, and $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. Applied to this problem with $x=\frac{5}{64}$, we have

$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$

From this, we can reconstruct approximations, and the denominator of these approximations will likely be the period. The wikipedia page on continued fractions explains that we get a series of approximate fractions $\frac{h_n}{k_n}$, where we set a numerator $h_n=b_nh_{n-1}+h_{n-2}$ and denominator $k_n=b_nk_{n-1}+k_{n-2}$, with initial values $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, and $k_{-2}=1$. This gives two sequences:

$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$

which gives three approximate fractions: $\frac{1}{12}$, $\frac{1}{13}$, and $\frac{5}{64}$. The last one is what we started with and is useless because 64 is too big (the period must be less than 35, after all). The first one is the actual period.

I don't know much about continued fractions but I think these approximations converge very quickly to the original fraction. So in practice, I think you would just check each denominator in the sequence of approximate fractions (in this case, both 12 and 13) since (a) there should not be that many approximate fractions, and (b) the final steps of Shor's algorithm are so inexpensive.