# Understanding Oracles for Simon's Algorithm

I'm having a hard time understanding oracles in Simon's algorithm. There are lots of discussions here and elsewhere for 2-qubit oracles, but when I go all the way up to 3 qubits, it's confusing. I've picked the secret string 110. From the usual descriptions of Simon's algorithm, I expect that I should measure either 000, 001, 110, or 111, as the mod-2 dot product of these four strings with 110 is 0, and thus they're the ones with non-zero amplitudes.

In my first oracle, I do a traversal and then, using my secret string 110, I add a CX from each of the high-order and middle-order qubits to their corresponding output qubits, like this (screenshots from IBM Quantum Composer, which treats q[2] as the most-significant input qubit. I cropped the outputs - all states not shown have zero amplitudes/probabilities):

You can see on the right that I don't get the expected results. I only get back 000 and 001. Messing about with the circuit, I found that using the high-order qubit on both output qubits gives me the results I expect:

This gives me 000 001, 110, and 111. This does the job and gives me what I expect, but I can't figure out why. Can anyone please help me understand how to think of the structure for Simon's problem oracles of more than 2 qubits, and also specifically why my first version failed but the second succeeded?

Thank you!

What you want to do here is concentrate on the controlled-nots. First of all, remember that two controlled-nots with the same control and the same target will cancel. So, in your first circuit, in effect, you only have a controlled not between $$q_0$$ and $$q_3$$.
Now, imagine you have the 3 control qubits $$q_0$$, $$q_1$$ and $$q_2$$ in a state $$|x\rangle$$ corresponding to a binary string $$x$$. After the controlled-nots, what will the state of the target qubits $$q_3$$ to $$q_5$$ be? $$q_0=x_0, q_4=q_5=0$$ (I'm writing these out explicitly because I will make a mistake with IBM's ordering of qubits otherwise). These are the two outputs that you're seeing. But note that, clearly, the problem's not set up right - Simon's problem is supposed to be that only two inputs give the same output where, here, you've got 4.
So, let's look at your second circuit. Now if you input $$q_0=x_0, q_1=x_1, q_2=x_2$$ then your outputs will be $$q_3=x_0, q_4=x_1\oplus x_2, q_5=0.$$ So, let's imagine we get a particular output $$y_0,y_1,0$$. What are the possible inputs? $$x_0=y_0$$ and $$x_1\oplus x_2=y_1$$. So, we could either have $$y_0,0,y_1$$ or $$y_0,1,\bar y_1$$. These two strings differ by the addition of $$0,1,1$$, your hidden string.
Now that you can understand that answer, the real question is how can you reverse the process? If I give you that the secret should be $$s$$, what sequence of controlled-nots do you want? I want a function, any function, such that $$f(x)=f(x\oplus s)$$. There are many choices. First note that for $$2^n$$ different input strings, there can only be $$2^{n-1}$$ different output strings. One simple assumption is to find a bit $$i$$ where $$s_i=1$$, and just say "the output $$f(x)_i$$ will be 0 for all $$x$$". Then add to that the assumption "if $$x_i=0$$ then $$f(x)=x$$". This is certainly not required, but makes things pretty easy.
At this point, we can proceed by doing controlled nots from the first register to the second on every matched pair of qubits except pair $$i$$. (In your example, $$i=2$$, so we have matched pairs $$(q_0,q_3)$$ and $$(q_1,q_4)$$, but don't do anything to pair $$(q_2,q_5)$$.) At this points, the unction is simply $$f(x)=x$$ on everything except bit $$i$$, which is 0. So, we're getting the right output for all $$x$$ where $$x_i=0$$. We just need to "fix" the output in the case where $$x_i=1$$. This is going to be easy as well, because we'll just be able to control some stuff off $$q_i$$ ($$q_2$$ in your case). What is it we need to achieve? We have an $$x0$$ and a $$y1$$ which are supposed to give the same output (I've put the bit value $$i$$ at the end for convenience), which will be $$x0$$, and our secret is $$s=\tilde s1$$. Hence, $$y=\tilde s\oplus x$$. If $$x_i=1$$, we just need to add $$\tilde s$$ to the other bits. So, we do this by doing a set of controlled-nots. They are all controlled off qubit $$i$$ in the first register, and target each of the qubits in the second register for which $$\tilde s=1$$. In your example, that's a controlled-not between $$q_2$$ and $$q_4$$.