# Thread: Help with Wikipedia Shor's Algorithm Derivation

1. ## Help with Wikipedia Shor's Algorithm Derivation

Looking at Shor's algorithm - Wikipedia, the free encyclopedia, I'm finding it hard to understand part of step four of the period-finding subroutine derivation. Why does w^(x0 * y) not contribute to the probability amplitude? It must be equal to unity but I don't understand why?

2. ## Re: Help with Wikipedia Shor's Algorithm Derivation

i find that hard to read (i know very little about quantum mechanics or computing) but it seems to me what is happening is this:

$\left|\sum_b \omega^{(x_0 + rb)y}\right| = \left|\sum_b \omega^{x_0y}\omega^{rby}\right|$

and since x0y is independent of b:

$= |\omega^{x_0y}|\left|\sum_b \omega^{rby}\right| = \left|\sum_b \omega^{rby}\right|$

since ω lies on the unit circle, and thus any power of it has magnitude 1 (whereas the sum of such unit vectors may not lie on the unit circle).

3. ## Re: Help with Wikipedia Shor's Algorithm Derivation

Thanks a lot - I definitely should have seen this!
Originally Posted by Deveno
i find that hard to read (i know very little about quantum mechanics or computing) but it seems to me what is happening is this: $\left|\sum_b \omega^{(x_0 + rb)y}\right| = \left|\sum_b \omega^{x_0y}\omega^{rby}\right|$and since x0y is independent of b: $= |\omega^{x_0y}|\left|\sum_b \omega^{rby}\right| = \left|\sum_b \omega^{rby}\right|$since ω lies on the unit circle, and thus any power of it has magnitude 1 (whereas the sum of such unit vectors may not lie on the unit circle).