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?

  • $\begingroup$ 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$? $\endgroup$
    – Tristan Nemoz
    Apr 2 at 12:20
  • $\begingroup$ No, i was wondering how many f's can we have that satisfies the condition in Simon algorithm, for a specific s, $\endgroup$ Apr 2 at 12:30

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$ Apr 2 at 14:39
  • 1
    $\begingroup$ And is probably should be $x\neq y\oplus s$ and $s\neq y\oplus s$ $\endgroup$ Apr 2 at 14:46
  • $\begingroup$ @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! $\endgroup$
    – Tristan Nemoz
    Apr 2 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.