# Shor's algorithm

1. Oct 9, 2007

### michael879

hey I have a quick question about this. I was trying to understand the QFT operator, so I manually used shor's algorithm to factor 15. I used 2 for the random number. My results seem a bit weird tho. below are the probabilities of observing each number (the correct answer is 4, since the period of 2^x mod 15 is 4). Also, I found that the probability of observing |x>|f(x)> is 1/4 the probability of |x>.

P(0) = 1/4
P(1) = 0
P(2) = 1/4
P(3) = 0
P(4) = 1/4
P(5) = 0
P(6) = 0
P(7) = 0
P(8) = 1/4
P(9) = 0
P(10) = 0
P(11) = 0
P(12) = 0
P(13) = 0
P(14) = 0
P(14) = 0

I find these results odd for two reasons.

1) there is a 1/4 probability of getting 0. I also did this for N = 6 and a = 5 and similarly found that P(0) = 1/2, which is very high for an obviously wrong answer. Not only that but in the N=6 example your more likely to find 0 as the answer than any of the other answers.

2) The only wrong answer that could possibly show up is 0. 2, 4, and 8 are all correct answers (since 8 is the period also, and searching multiples of the returned result are part of the algorithm so that 2 would work since 2*2=4).