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

I Simon's Algorithm

  1. Oct 10, 2016 #1
    Hi all, I am sure some of you have heard of Simon's algorithm that calculates a secret string s when given a black box. Basically, let's say we have a qubit x that is n digits long. Now the black box contains a function f that outputs f(x+s) where s is the mystery string and + is bit-wise modulo 2 addition. For Simon's algorithm, you apparently need like n-1 equations and stuff but I don't understand why this is necessary. For example, let's say the secret string s=101.

    Then if input was 000, we have 101

    From here, we already know the secret string. What is the purpose of going any further, is it not trivial what this secret string is? Can someone please explain this to me?
  2. jcsd
  3. Oct 10, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    At least according to the wikipedia description, the function can be much more general than just bitwise addition. As a subset (!), all n! permutations are possible.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted