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


You could do something like:

  • 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.

  • $\begingroup$ how is the most significant bit chosen/defined? $\endgroup$
    – Ronen Raz
    Jun 25 '19 at 11:55
  • $\begingroup$ Well, really, you can make it any bit for which $s$ is 1. $\endgroup$
    – DaftWullie
    Jun 25 '19 at 15:06

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.