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$?

  • 1
    $\begingroup$ 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)$? $\endgroup$ Feb 10 at 5:15

Your Answer

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

Browse other questions tagged or ask your own question.