I Simon's Algorithm: Solving the Mystery of f(x+s)

[Aakash Lakshmanan]

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?

 

[mfb]

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.