1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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...