# Help with Wikipedia Shor's Algorithm Derivation

• December 24th 2012, 02:27 AM
StaryNight
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?
• December 24th 2012, 02:55 AM
Deveno
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).
• December 24th 2012, 04:56 AM
StaryNight
Re: Help with Wikipedia Shor's Algorithm Derivation
Thanks a lot - I definitely should have seen this!
Quote:

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).