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


1 Answer 1


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, 2019 at 11:55
  • $\begingroup$ Well, really, you can make it any bit for which $s$ is 1. $\endgroup$
    – DaftWullie
    Jun 25, 2019 at 15:06
  • $\begingroup$ @DaftWullie how does one think of making an oracle via the process you define, is it intuition based? $\endgroup$
    – Upstart
    Apr 4, 2023 at 21:33
  • $\begingroup$ @Upstart I guess it verges on that eventually. There's a logical process that, simply, the more often you do it, becomes more intuitive and you forget exactly how you did it originally! I suppose my thinking went something along the lines of "I need to divide the input space into pairs, and I need to decide a function that each of those pairs will return. What will that function be? Could be anything so long as the outputs from the different pairs are distinct. But let's make it easy and have the output just be one of two strings in the pair. We can always add any extra function on the top. $\endgroup$
    – DaftWullie
    Apr 5, 2023 at 6:49
  • $\begingroup$ So, my pairs must be of the form $x$ and $x\oplus s$, both returning $x$. How do I make that happen? How do I decide which one will be the one I return? Well, $x$ and $x\oplus s$ must differ somewhere. So, let's make an arbitrary choice that, in the first place where they differ, the one that's 0 is the one that's returned unchanged. The other one, $x\oplus s$ must be returned as $(x\oplus s)\oplus s$. So, that's the classical logic working. Can I implement that as a reversible quantum circuit? I must be able to. $\endgroup$
    – DaftWullie
    Apr 5, 2023 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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