# How many oracles can satisfy a solution of Simons problem?

I know that the f/oracles in Simons algorithm is 2-1, and that $$f(x)=f(y)\iff y=x\oplus s$$. My question is if we can have gave different oracles/functions, that has the same codomain/output for a given s. And if so how many such oracles can we have ? And is there a way to compute how many?

• I'm not sure to understand your question, are you asking, for a given $f$ satisfying Simon's promise, how many unitaries $U_f$ are there such that $U_f|x,y\rangle=|x,y\oplus f(x)\rangle$? Apr 2 at 12:20
• No, i was wondering how many f's can we have that satisfies the condition in Simon algorithm, for a specific s, Apr 2 at 12:30

Let $$f:\{0, 1\}^n\to\{0,1\}^m$$ satisfying Simon's promise for a given $$s$$. We want to count how such many $$f$$ are there.

Let us assume $$s\neq 0$$ for now. Let $$S_0$$ be a subset of $$\{0, 1\}^n$$ such that $$\left|S_0\right|=2^{n-1}$$ and such that for all $$x,y\in S_0$$, $$x\neq y\oplus s$$. Basically, if we know $$f$$ on $$S_0$$, we completely know $$f$$ on $$\{0, 1\}^n$$. Let us denote $$x_1,\cdot,x_{2^{n-1}}$$ the elements of $$S_0$$.

• We first choose $$f\left(x_1\right)$$, for which we have $$2^m$$ choices.
• We then choose $$f\left(x_2\right)$$, for which we have $$2^m-1$$ choices.
• ...
• We then choose $$f\left(x_{2^{n-1}}\right)$$, for which we have $$2^m-2^{n-1}+1$$ choices.

All in all, this results in $$\prod\limits_{i=0}^{2^n-1}\left(2^m-i\right)=\frac{2^m!}{\left(2^m-2^{n-1}\right)!}$$ functions.

If $$s=0$$, a similar reasoning yields $$\frac{2^m!}{\left(2^m-2^n\right)!}$$ functions.

• Thank you, just to dobbel check. The reason $|S_{0}|=2^{n-1}$ is because f is 2 to 1, so we only map to half of the possible states? Apr 2 at 14:39
• And is probably should be $x\neq y\oplus s$ and $s\neq y\oplus s$ Apr 2 at 14:46
• @PinkElephants Yes, once you hav chosen $f(0)$ for instance, the value of $f(s)$ is forced. So, once you have chosen a value for half the possible inputs, the rest of them is forced. Nice catch for your second comment! Apr 2 at 14:53