Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Shor's algorithm

  1. Oct 9, 2007 #1
    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).
     
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted



Similar Discussions: Shor's algorithm
  1. Shor's algorithm (Replies: 2)

  2. DFT algorithm (Replies: 2)

  3. Grover's algorithm (Replies: 7)

Loading...