# Coding an oracle for Simon's algorithm

I am trying to implement Simon's algorithm which calls for a 2-to-1 mapping function that satisfies $$f(x) = f(x⊕s)$$.

I am looking for a simple way to code the oracle (using $$H$$, $$Cx$$, and $$R$$ gates), ideally with an easy way to redefine $$s$$.

• assume the most significant bit of $$s$$ is 1.
• write a function that says "if the most significant bit of $$x$$ is 0, return $$x$$. if the most significant bit of $$x$$ is 1, return $$x\oplus s$$.
This is easily implemented because you start by doing a transversal set of cNOT gates to copy $$x$$ from the input register to the output register. Then, you simply do a bunch of controlled-not gates controlled off the most significant bit of the first register, targeting each of the qubits in the output register for which the corresponding bit of $$s$$ is 1.
• Well, really, you can make it any bit for which $s$ is 1. – DaftWullie Jun 25 at 15:06