4
$\begingroup$

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?

enter image description here

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ As you were writing, I was trying to a solution too above. But you see I still don't know what's going on. See my attempted solution there. See if you spot what I'm missing here. I don't know how you got to $1/12$ and $1/13$. I guess I don't know how you got your $k$ list. I guess I'm going to need to review this Wikipedia article. $\endgroup$
    – user14021
    Dec 5, 2020 at 19:38
  • 1
    $\begingroup$ It looks like what you did was worked backwards through your continued fraction expansion (what I called "$a_n$"). But it's a different process to produce the best approximate fractions. Consider that you have $\frac{1}{12 + \dots}$. Remove the $\dots$ and you get the first approximation. Then you have $\frac{1}{12+\frac{1}{1+\dots}}$. Remove the dots again and you get the second approximation. $\endgroup$
    – Sam Jaques
    Dec 5, 2020 at 20:09
  • $\begingroup$ Alright! That's helpful. Then like you I do find the sequence $1/12, 1/13, 5/64$. You say $64$ cannot be so it must be either $13$ or $12$ and checking both we find $12$ works. Now here's what happens to $11$. I get the sequence $1/5$, $1/6$, $5/29$, $11/64$. None works. But $6$ is a divisor of $12$. Is that why it is said that Shor's algorithm sometimes produces a divisor of the order? $\endgroup$
    – user14021
    Dec 5, 2020 at 20:24
  • $\begingroup$ Also interesting that the answer I wanted was $1/12$ which is the first approximation. It seems that as I got better and better approximations, the desired result got lost. Is this really right? $\endgroup$
    – user14021
    Dec 6, 2020 at 15:42
  • $\begingroup$ By the way, I'd love if you would consider this question. It's the same thing we discussed here, but now in the discrete log context. Thank you! $\endgroup$
    – user14021
    Dec 7, 2020 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.