3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – P_Gate Feb 4 at 16:57
  • $\begingroup$ 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? $\endgroup$ – DaftWullie Feb 5 at 8:40
  • $\begingroup$ 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" $\endgroup$ – user4961 Feb 5 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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