<blockquote>
  <p>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 $&lt;N$ and if we don't find $r$
  as one of the convergents do we just
  start again?</p>
</blockquote>

<p>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.</p>

<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2011-04-17T08:25:27.083Z
I like how you refer to the paper as "Shor's paper" :)
Suresh Venkat
CC BY-SA 3.0
2011-04-18T09:24:48.843Z
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
CC BY-SA 3.0
2011-11-15T19:25:36.840Z
If $r=2^t$, then indeed all the possible values of $j$ will have an equal probability of $1/2^t$.
Peter Shor 
CC BY-SA 3.0
2011-04-17T06:28:07.450Z
2011-11-15T19:24:41.753Z
2011-11-15T19:24:41.753Z
Peter Shor 
<p>I'm having a little trouble fully understanding the final steps of Shor's factoring algorithm.</p>

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

<p>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.</p>

<p>Here's where I'm a little hazy:</p>

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

<p>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 $ &lt; N $ and if we don't find $ r $ as one of the convergents do we just start again?</p>

<p>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?</p>

<p>Just a little confused as some papers seem to say different things.</p>

<p>Thanks.</p>

CC BY-SA 3.0
2011-04-14T14:31:55.767Z
@Peter Shor might even help you with this one.
Dave Clarke
CC BY-SA 3.0
2011-04-16T10:21:03.113Z
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
<quantum-computing>
Shor's factoring algorithm help
Callum
# Shor's factoring algorithm help

(Asked by: username_0 on 2011-04-14)

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.

**Tags:** quantum-computing

> **Comments:**
> **username_1**: @username_2might even help you with this one.  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2011-04-17. Score: 47 | Accepted answer

> 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 $

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.

> **Comments:**
> **username_3**: I like how you refer to the paper as "Shor's paper" :)  
> **username_0**: 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.  
> **username_2**: If $r=2^t$, then indeed all the possible values of $j$ will have an equal probability of $1/2^t$.  

---

