28
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 21
    $\begingroup$ @Peter Shor might even help you with this one. $\endgroup$
    – Dave Clarke
    Commented Apr 14, 2011 at 14:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Callum
    Commented Apr 16, 2011 at 10:21

1 Answer 1

Reset to default
47
$\begingroup$

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.

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

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.