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.

  • 21
    @Peter Shor might even help you with this one. – Dave Clarke Apr 14 '11 at 14:31
  • 1
    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. – Callum Apr 16 '11 at 10:21
up vote 47 down vote accepted

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.

  • 33
    I like how you refer to the paper as "Shor's paper" :) – Suresh Venkat Apr 17 '11 at 8:25
  • 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. – Callum Apr 18 '11 at 9:24
  • 3
    If $r=2^t$, then indeed all the possible values of $j$ will have an equal probability of $1/2^t$. – Peter Shor Nov 15 '11 at 19:25

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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