I am trying to implement a quantum bit string comparator (QBSC) circuit (based on this paper) into a simple Grover's algorithm but I am unfortunately running into issues. The paper has two circuits: the actual bit string comparator,
and the implementation as a Grover Oracle,
Basically, the concept is that if you take the measurement on the $O_1$ and $O_2$ states, depending on the output you are able to assess if the bit string a is bigger, equal, or smaller than the bit string b (the bit strings are encoded in binary on the qubits a1, b1, a2, etc...). The second circuit is supposed to be an implementation in a Grover iteration, and it is not totally clear from the schematic how it is implemented. In the circuit, the bit string b is made to be into a superposition.
I have tried to create the latter circuit based on my knowledge of Grover's algorithm but cannot make it work.
My first assumption was that the ancillary qubit in the $|-\rangle$ state was simply connected to the $|O_1\rangle$ state with a CNOT gate (which seems to be what the schematic shows). I also did the math on paper, and the gate does make the phase kickback on the wanted state. I also implemented the diffusion operator, but I think this is where my mistake lies.
My first thought, seeing that the formal definition of the operator is to work the reflection on the superposition of states, was to apply the diffusion operation only onto the b qubits and then measure those to get the marked states with a higher probability. So my circuit is such:
where I compare the string a = 010 to b in superposition. This should output me a lower probability of getting the bellow values 000, 001, and 010 (I don't care about the number of iterations at the moment, I just want to see that these are less probable than the other solutions), but I get an equal probability of all the states.
So then I thought that I might have to diffuse on all of the qubits, as they all take part in the phase kickback etc, but it just lead to the same result...
Would anybody have an idea of how to implement this circuit correctly? Or know what are my missteps? I don't have a huge background in QC, but have read the Nielsen book and understand the topic. I think I simply miss actual applications of it and as such may not understand how to really implement the algorithm itself and where to use the diffusion operator etc...
Thank you so much in advance!