Solving Shor's Algorithm to Factor 15: Results & Analysis

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

 

[azntoon]

But why would the probability of 0 be 1/4? Shouldn't it be 0 since its wrong?It seems like this is an issue with the algorithm itself, but I'm not sure. Can anyone help me understand why this might be happening?

 

[denian]

I find these results interesting and worth further investigation. It is important to understand the QFT operator and how it affects the outcome of Shor's algorithm. It is possible that there may be a flaw in your manual implementation of the algorithm or in the way you are calculating the probabilities. It would be helpful to compare your results with those obtained through a computer simulation or by using a different method to calculate the probabilities. Additionally, exploring different values of N and a could provide more insight into the behavior of the algorithm and the QFT operator. Overall, further analysis and experimentation would be necessary to fully understand these results and their implications for Shor's algorithm.