Simon's Problem

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.