Using Quantum Bit String Comparision inside Grover's algorithm

Question

Intro

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.

Question

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!

Answer 1

The problem is actually in the oracle.

First, $O_1$'s state is 1 if $a$ (the constant which you are checking against) is greater than $b$, so 000 and 001 will be the only marked states: you want $O_2$ which is 1 if $a$ is less than $b$.

Second, the oracle needs to flip the amplitude of marked states through the CNOT with the ancilla but not otherwise change the state that goes in, thus, after flipping the ancilla, the circuit needs to be inverted. Luckily, all the base gates used are their own inverses so this is just a matter of mirroring: a Quirk picture similar to yours is shown below, where UCT is the mirror of UC when reduced down to its controls and X gates:

In addition, after all this, you should actually find that everything has went backwards and the probabilities of 000, 001, and 010 have increased while the others have lowered. This is, unfortunately, an inherent quirk of Grover's Algorithm that is caused by there being more right than wrong answers: with more marked than unmarked, the mean will be negative and thus the inversion across the mean will increase the amplitude of the unmarked states instead. In practical cases, this is normally not a big deal since Grover's Algorithm is a search algorithm and if there are more correct answers than wrong answers one could simply guess and will be more than 50% likely to be right.