Shor's factoring algorithm help

Question

I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm.

Given an $N$ we want to factor, we choose a random $x$ which has order $r$.

The first step involves setting up the registers and applying the Hadamard operator. The second step a linear operator is applied. The third step the second register is measured (I believe this step can be performed later instead). The fourth step the discrete Fourier transform is applied to the first register. Then we measure the first register.

Here's where I'm a little hazy:

We get a measurement in the form $\mid j , x^k \textrm{mod} N \rangle $.

From this we can find the convergents of the fraction $ \frac{j}{2^q} $ , the convergents are possible values of the order $ r $. Here do we just try all the convergents $ < N $ and if we don't find $ r $ as one of the convergents do we just start again?

Also how does the probability for possible values $ j $ differ? They way I see it they should all have the same probability but Shor's paper says this isn't the case?

Just a little confused as some papers seem to say different things.

Thanks.

• Dave Clarke: @Peter Shor might even help you with this one.
• Callum: Since asking this questions I think I have a better understanding of it. To clarify for those that are interested, we do get a measurement in the form $ \mid j , x^k \mod N \rangle $ where all we need is the $ j $. The value $ j $ can be written as $ j= 2^q k/ r $ by dividing through by $ 2^q $ we get $ k/r $ and from this we can find its convergents, the denominator $ < N $ of a convergent is a possible value of $ r ,ドル if it is not the algorithm is run again. The likelihood of finding $ j $ is based on a sum which depends on the value of $ 2^q $ and what the period $ r $ is.

Answer 1

From this we can find the convergents of the fraction $j/2^q$ , the convergents are possible values of the order $r.$ Here do we just try all the convergents $<N$ and if we don't find $r$ as one of the convergents do we just start again?

You could; the algorithm works fairly fast if you do. If you want to reduce the expected number of quantum steps, you could also do some other tests; for example you should check whether $r$ is a small multiple of one of the convergents. But if you don't find $r$ after these extended tests, you need to start again.

Also how does the probability for possible values $j$ differ? They way I see it they should all have the same probability but Shor's paper says this isn't the case?

I don't know whether I can help you more with this, because you haven't given me enough information for me to tell why you're confused. The probability for each value of $k$ in the fraction $k/r$ is (very nearly) the same. However, depending on exactly where $k/r$ falls between the adjacent values of $j/2^q$ and $(j+1)/2^q,ドル the probabilities of the specific values of $j$ differ.

• Suresh Venkat: I like how you refer to the paper as "Shor's paper" :)
• Callum: I'm just a little unsure on how the probability works thats all. Am I right in saying that $ \textrm{Prob} (j) = \frac{1}{2^q \times ([ \frac{2^q - k -1}{r}]+1)} \Bigg| \sum^{[ \frac{2^q - k -1}{r}]}_{a=0} e^{ -2 \pi i rja/2^q } \Bigg| ^2 $. In the examples I've seen there has been a symmetry on the probability distribution about the mid-point of the $x$-axis, is this always the case? Suppose that $ r= 2^t ,ドル does this mean that for all possible values of $ j= \frac{ k_0 2^q}{r} ,ドル where $k_0 = 0, \cdots , r-1 ,ドル all $ j $ will have an equal probability of $ \frac{1}{2^t} $? Thanks.
• Peter Shor: If $r=2^t,ドル then indeed all the possible values of $j$ will have an equal probability of 1ドル/2^t$.