1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

When you implement a quantum oracle (or any quantum operation that has to act on quantum registers in superposition), you cannot use classical tricks like stopping the comparison of bits once you've made your decision, since the computation has to be linear, so you have to examine all bits.

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

$\endgroup$
2
  • $\begingroup$ Thanks a lot for your explanations and for the link to the quantum library. $\endgroup$
    – Cyrano
    Commented Jan 15 at 9:43
  • $\begingroup$ @Cyrano I'm glad that helped! If your question is answered, you can mark the answer as accepted using the checkmark next to it. This way other community members will know it's resolved, and the bot will not bump it to the recent questions half a year later $\endgroup$ Commented Jan 16 at 4:28

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.