Simon’s problem is a simple problem to describe.
You are to find a string $ s \in \{0,1\}^n $.
The only way you can find $ s $ is to evaluate a function:
$ f: \{ 0 , 1 \}^n \rightarrow \{ 0 , 1 \}^n $
The only information you have about $ f $ is that when $ x \neq y $:
$ f(x) = f(y) \Leftrightarrow x \oplus y \in \{ 0^n, s \} $
The goal is to find $ s $ with as few evaluations of $ f $ as possible.
Features of the Problem
There is a difference for one particular value of $ s $.
When $ s $ is the all zero string $ 0^n $, different inputs must give different outputs for $ f $.
Since the domain and codomain of $ f $ are both $ \{ 0 , 1 \}^n $, then $ f $ must be bijective.
Otherwise, $ s $ is not equal the all zero string.
Then for every $ x $ in $ \{ 0 , 1 \}^n $ there is a unique $ y \neq x $ such that $ f(x) = f(y) $ and $ x = y \oplus s $.
This means that the image of $ f $ is half the size of the domain.
By size we mean cardinality.
Example
Suppose $ f: \{0 , 1\}^3 \rightarrow \{0, 1 \}^3 $ and $ s = 010 $.
Then $ f $ might be as follows.
$ f(000) = 000 \qquad $ $ f(001) = 111 \qquad $ $ f(010) = 000 \qquad $ $ f(011) = 111 $
$ f(100) = 101 \qquad $ $ f(101) = 110 \qquad $ $ f(110) = 101 \qquad $ $ f(111) = 110 $
Or, for a different example, $ f $ might be as follows.
$ f(000) = 110 \qquad $ $ f(001) = 000 \qquad $ $ f(010) = 110 \qquad $ $ f(011) = 000 $
$ f(100) = 111 \qquad $ $ f(101) = 100 \qquad $ $ f(110) = 111 \qquad $ $ f(111) = 100 $
Complexity
How many times must we call $ f $ to determine $ s $?
Best Case
In the best case scenario, we might figure $ s $ out in our first two calls to $ f $.
This will happen if we get the same output for two different inputs, $ x $ and $ y $.
Then $ s $ is just $ x \oplus y $.
For instance, in the first example above, if we call $ f(110) $ we get $ 101 $.
If we then call $ f(100) $ we get $ 101 $ so we have found $ f(x) = f(y) $.
Then $ s $ is equal to $ 110 \oplus 100 $ which is $ 010 $, the right answer.
Worst Case
In the worst case scenario, we call $ f $ a total of $ 2^{n-1} $ times and get a different output each time.
This is possible whether $ s $ is $ 0^n $ or not.
Indeed, when $ s $ is $ 0^n $ this will definitely happen.
Then the next call will either give another distinct output or won’t.
If it does, then $ s $ must be $ 0^n $.
Otherwise, we combine the two inputs giving the same output using xor to find $ s $.
So, we called $ f $ a total of $ (2^{n-1}+1) $ times.