# How write a marking oracle if greater than with Q#?

I'm trying to write a code to find a minimum in a list. I follow this paper : A quantum algorithm for finding the minimum. So I need to write an operator to mark the case $$T [j] < T[y]$$.

My idea is to use the method describe here:

In order to manually determine the greater of two binary numbers, we inspect the relative magnitudes of pairs of significant digits, starting from the most significant bit, gradually proceeding towards lower significant bits until an inequality is found. When an inequality is found, if the corresponding bit of A is 1 and that of B is 0 then we conclude that A>B.

So I wrote this code:

    operation MarkIfGreaterThan(c0 : Qubit[], c1 : Qubit[], target : Qubit) : Unit is Adj+Ctl {
use q0IsGreaterThanQ1 = Qubit();
use isFirstDifference = Qubit();
for (q0, q1) in Zipped(c0, c1) {
// do as https://en.wikipedia.org/wiki/Digital_comparator
// https://pyqml.medium.com/the-quantum-bit-comparator-463911f7bcd3
X(q1);
CCNOT(q0,q1,q0IsGreaterThanQ1);
X(q1);

// How to find out a way to don't repeat the code above for the less significant qbits
X(isFirstDifference);
CCNOT(q0IsGreaterThanQ1,isFirstDifference,target);
}
}


I'm wondering how find a way to "stop" the loop i.e don't affect my target qubit for the less significant qubits. I find this paper but in this quantum circuits they apply the comparison for all bits. In my situation I just want compare the most significant.

One idea would be to record the comparisons in an array of qubits (q0IsGreaterThanQ1[]) and then go through this array to stop at the value representing my most significant qubit. However, this would cost me unnecessary qubits. And as you know, we need to save them.

You're not comparing two bit strings, you're comparing two states, each of which is in superposition. Let's say you're comparing $$|00\rangle + |11\rangle$$ with $$|01\rangle + |10\rangle$$, first bit is the most significant. Classically, you compare each value separately, and you can say that 00 is less than 01 and 10 but 11 is greater than both of those; sometimes you only need to compare the most significant bit for this, but if that bit is the same, you need to compare the least significant bit as well. In the quantum scenario, you need to come up with a unitary transformation that is correct on all pairs of basis states but also is linear, so that it can be applied to states in superposition. The only way to stop after comparing the most significant bit would be to measure the comparison outcome, but that would collapse the superposition, so you would not be able to use this comparison as part of Grover's search algorithm implementation.
To answer the question itself, there are different algorithms of implementing integer comparison (all inspecting all qubits), one implementation is Q#'s library GreaterThan (see https://github.com/microsoft/QuantumLibraries/blob/a943e7087a45bbfcac57aea916d34c619d69325e/Standard/src/Arithmetic/Integer.qs#L474 for the code).