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.