# How can I solve Simon's problem for the projection function $f(x_0,x_1)=x_0$?

I am having issues solving Simon's problem for a projection function.

The function $$f: \{0,1\}^2 \mapsto \{0,1\}$$ defined as $$f(x_0,x_1) = x_0$$ returns the least significant bit of its argument.

How can I solve Simon's problem for this function? And write down the corresponding number $$a$$?

• I'm not sure how Simon's problem, which deals with a black box function of equal input and output bitstring size, would generalize to this situation. You could argue that the output could be defined as $f(x_0, x_1) = (x_0, 0)$ to make it the same length, and then the $a \in \{0, 1\}^2$ that isn't $(0, 0)$ such that $f(x \oplus a) = f(x)$ would be $(0, 1)$, but that's not really a useful question or answer. Might you be thinking of a projection function in the idempotent sense where $f: \{0, 1\}^n \mapsto \{0, 1\}^n$ has the property $f^2(x) = f(x)$? Feb 10 at 5:15