# In Simon's algorithm, why is $f$ one-to-one if (and only if) $s=0^n$?

I'm dealing with Simon's algorithm a bit and "stumbled" upon something called for the algorithm. It is said that if the period is $$s = 0^n$$, then it is an injective function, that is, a 1 to 1 function. How can you show that this is so?

Then I would be interested. Moreover, if that is not the case, so $$s \neq 0^n$$, then why is it a 2 to 1 function?

This is basically the definition of the type of function that you apply Simon's algorithm to. You are required to have a function $$f(x)$$ such that $$f(x)=f(y)$$ if and only if $$x\oplus y=0$$ or $$s$$.

Hence, if $$s$$ is all zeros, the outcomes are all unique: if $$f(x)=f(y)$$ then $$x=y\oplus 000\ldots 0$$, but bitwise addition modulo with 0 doesn't change the bit values, so $$x=y$$.

On the other hand, if $$s$$ is non-zero, there are exactly two values that give the same value of $$f(x)$$ since $$x\oplus00\ldots 0=x$$, just leaving the distinct $$y=x\oplus s$$.

To add, following a comment. I suspect we need to go further back and understand the notation better. There is a function $$f(x)$$. It accepts, as an argument, a sequence of $$n$$ bit values, which we write as a variable $$x$$ (we write $$x\in\{0,1\}^n$$ as a shorthand for conveying it's made up of $$n$$ bit values). The answer is a sequence of $$n$$ bit values, which we write as $$y=f(x)$$. We are promised that $$a$$, also a sequence of $$n$$ bit values exists such that $$f(x)=f(x\oplus a).$$ The calculation $$x\oplus a$$ has a very specific meaning; we take each bit of $$x$$ (call the $$i^{th}$$ bit $$x_i$$) and each bit of $$x$$ and return the sequence where they have been added together modulo 2: $$x_i\oplus a_i=x_i\text{ XOR }a_i=x_i+a_i\text{ mod }2=\left\{\begin{array}{cc} 0 & x_i=a_i \\ 1 & x_i\neq a_i\end{array}\right.$$ So, for example $$00110\oplus 01010=01100.$$ A key feature of this bitwise addition function is that $$x\oplus a\oplus a=x.$$

An example of a suitable $$f(x)$$ is $$\begin{array}{c|cccccccc} x & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ f(x) & 010 & 011 & 000 & 001 & 010 & 011 & 000 & 001 \end{array}$$ Here, you can see that each value of $$f(x)$$ is repeated exactly twice. So, we find two values of $$x$$ that give the same output, say $$001$$ and $$101$$. These correspond to values $$x$$ and $$x\oplus a$$, so we can find $$a$$ with $$a=x\oplus(x\oplus a)=001\oplus101=100.$$ Then you can check for every $$x$$ that $$f(x)=f(x\oplus 100)$$.

• Thanks for your answer, maybe I should clarify something, what I mean. I found this in a lecture: $f(x) = f (x \oplus a)$ (That's understandable for me, I think of the real sine with $+2\pi$ and without). Now it comes: $x, y \in \{0,1\}^n, \text{if } x \neq y \oplus a, \text{ then } f(x) \neq f(y)$ this part is not understandable to me, what does that say? Thank you for your help! – P_Gate Feb 4 '19 at 16:57
• I suspect there's something you've misunderstood, and we haven't yet stepped far enough back to unpick what the problem is. Where does the sine function come into it? – DaftWullie Feb 5 '19 at 8:40
• The sine does not have to do with that at first, only when I think of a periodic function, I first think of the sine. For this applies yes: $sin(x)=sin(x+2\pi)$. And starting from the sinus example, I could think of this as well: $f(x)=f(x\oplus a)$ My problem was simply because I also found this in a lecture, which was not completely understandable for me:$x, y \in \{0,1\}^n, \text{if } x \neq y \oplus a, \text{ then } f(x) \neq f(y) \text{ "Eq: 1"}$ I can follow your explanation. Unfortunately this does not answer my implicit question: See "Eq: 1" – user4961 Feb 5 '19 at 12:37