Implementing the Oracle in Grover

Question

I need your expert opinions/comments on this problem.

Suppose I have a database (say 16 entries), such that db[0] = 0.12, db[1] = 0.84, db[2] = 0.55, ..., db[15] = 0.91. I want the oracle to mark those indexes whose value is > 0.8 (for example). In this case the oracle should mark the index of 1 & 15 so that the Grover algo is able to pick out one of the desired index after a certain number of iterations. How should I go about doing this?

My solution (I use Q#):

1. I create 4 quantum registers; targetReg, yReg, x1Reg, x2Reg.
2. x1Reg has 4 qubits, representing the database indices and in uniform superposition.
3. x2Reg has qubits enough to represent the real numbers associated with each index. In this case, 7 qubits is suffice (I can simply multiply the values by 100 so that they become integers).
4. yReg has the same number of qubits as x2Reg and initialized to 0.8 (or 80 after multiplication).
5. targetReg has a single qubit.
6. Start iteration {
7. within {Compare yReg and x2Reg and set yReg to |0> if x@Reg > yReg.}
8. apply {ControlledOnInt(0, X)(yReg, targetReg)}.
9. Then perform the reflection.
10. } End iteration.
11. Measure x1Reg.

Is this how it should be done? I have not actually tried it yet but I believe it should work although I have no clue how to implement Item 7 (the comparison). I was wondering if there are other alternate ways of doing it.

Edit: I have written a Q# program that finds and marked entries that are equal to the desired entry. It seems to be working fine although my apologies if my code looks amateurish since I only started to learn Q# a month ago. Now I need to find out how to find and marked entries that are greater than the desired entry.

operation GroverSearchIntDatabase() : Unit {

    let indexRegLength = 4;  // number of qubits to represent the database indices
    let intRegLength = 7;  // number of qubits to represent the integers
    
    // Generate the database randomly
    let databaseSize = 2 ^ indexRegLength;
    mutable database = [0, size = databaseSize];
    for idx in 0 .. databaseSize - 1 {
        set database w/= idx <- DrawRandomInt(0, (2 ^ intRegLength) - 1);
    }
    
    // Randomly select an index pointing to the desired integer
    let solutionIndex = DrawRandomInt(0, databaseSize - 1);
    let solutionInt = database[solutionIndex];
    Message($"The desired integer: {solutionInt}");
    
    // Find out how many indices have the same desired integer
    let predicate = EqualI(_, solutionInt);
    let nSolutions = Count(predicate, database);
    Message($"Number of indices with the same integer: {nSolutions}");
    
    // Initiailize the quantum registers
    use indexReg = Qubit[indexRegLength];
    use intReg = Qubit[intRegLength];
    use desiredIntReg = Qubit[intRegLength];
    use targetReg = Qubit();
    
    let nIterations = Floor(Sqrt(IntAsDouble(databaseSize) / IntAsDouble(nSolutions)) * PI() / 4.0);
    mutable measuredIndex = 0;
    
    // Theoretical success probability
    let success_prob = Sin((2.0 * IntAsDouble(nIterations) + 1.0) * ArcSin(Sqrt(IntAsDouble(nSolutions)) / Sqrt(IntAsDouble(databaseSize)))) ^ 2.0;
    Message($"Success probability: {success_prob}");
    
    // Grover Search
    ApplyToEach(H, indexReg);
    
    for _ in 1..nIterations {
    
        // This is the oracle
        within {
            X(targetReg);
            H(targetReg);
            
            // Associate the integers to the corresponding indices
            for idx in 0 .. databaseSize - 1 {
                ControlledOnInt(idx, ApplyXorInPlace)(indexReg, (database[idx], LittleEndian(intReg)));
            }

            // Set the desiredIntReg to |0> if it is equal to solutionInt
            ApplyXorInPlace(solutionInt, LittleEndian(desiredIntReg));
            for (q0, q1) in Zipped(intReg, desiredIntReg) {
                CNOT(q0, q1);
            }
        } apply {
            ControlledOnInt(0, X)(desiredIntReg, targetReg);
        }
        
        // This will be the reflect about uniform
        within {
            ApplyToEachA(H, indexReg);
            ApplyToEachA(X, indexReg);
        } apply {
            Controlled Z(Most(indexReg), Tail(indexReg));
        }
    }
    set measuredIndex = MeasureInteger(LittleEndian(indexReg));
    Message($"Desired integer: {solutionInt}, Integer of measured index: {database[measuredIndex]}");
    
}

Answer 1

Simply use the GreaterThan operation. Success rate is around 0.96 if there is only one index whose integer is greater out of 16 entries.

Below is the Q# code for the oracle.

within {
         X(targetReg);
         H(targetReg);

         // Associate the integers to the corresponding indices
         for idx in 0 .. databaseSize - 1 {
               ControlledOnInt(idx, ApplyXorInPlace)(indexReg, (database[idx], LittleEndian(intReg)));
         }

         ApplyXorInPlace(solutionInt, LittleEndian(desiredIntReg));
       } apply {
         GreaterThan(LittleEndian(intReg), LittleEndian(desiredIntReg), targetReg);
       }

Answer 2

Your algorithm seems to be correct, though you may have done a typo at 7. and I'm not sure about what the ControlledOnInt gate does. So that we're aligned:

7. Flip targetReg to $|1\rangle$ if x2Reg $>$ yReg
8. Apply a $Z$ gate on targetReg, which will phase-flip the states we're interested in
9. Flip targetReg to $|0\rangle$ if x2Reg $>$ yReg to disentangle targetReg from the rest of the state

This is how to build the oracle in your case. Now, your question is, "how to perform the seventh and ninth steps"? Essentially, what you want to do is a comparer. Note that in order to do that, you will probably need one more qubit and use this qubit and the targetReg qubit as ancillaes, as specified in this answer.

Implementing such an algorithm may be quite complex however, since it requires you to implement several quantum routines (adder, incrementer, ...), but it is the most efficient one "qubits-wise". I would recommend taking the time to understand it and choosing this solution if possible.

A simpler scheme but also (way) less efficient is simply testing for bitwise equality. Let us assume that you want to compare a quantum register $a$ to a constant $b$. Then the following scheme would work: The idea is the following : test whether the MSB of $a$ and $b$ are different. If that's the case, then you have found your result. If that's not the case, you have to move on to the next bit.

Though this seems simple, you will need $n+1$ ancilla qubits to do this (which in your case is not that critical since it removes you the need for the yReg register). Indeed, the "uncomputation" step requires a new ancilla each time (at least to the best of my knowledge). At the end of the routine, you can apply a $Z$ gate on the "Result" qubit and then uncompute all your ancillaes and result qubit.