Implementing the Oracle in Grover

Question 1

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#):

I create 4 quantum registers; targetReg, yReg, x1Reg, x2Reg.
x1Reg has 4 qubits, representing the database indices and in uniform superposition.
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).
yReg has the same number of qubits as x2Reg and initialized to 0.8 (or 80 after multiplication).
targetReg has a single qubit.
Start iteration {
within {Compare yReg and x2Reg and set yReg to |0> if x@Reg > yReg.}
apply {ControlledOnInt(0, X)(yReg, targetReg)}.
Then perform the reflection.
} End iteration.
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 areequal to the desired entry. It seems to be working fine although my apologies if my code looksamateurish since I only started to learn Q# a month ago. Now I need to find out how to find and marked entries that aregreater 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]}");    }

Question 2

Simply use theGreaterThan 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);       }

Question 3

I've edited your question and answer to match the Q&A format. Nice job on getting your answer and +1 for having posted it!

Question 4

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

FliptargetReg to$|1\rangle$ ifx2Reg$>$yReg
Apply a$Z$ gate ontargetReg, which will phase-flip the states we're interested in
FliptargetReg to$|0\rangle$ ifx2Reg$>$yReg to disentangletargetReg 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 thetargetReg qubit as ancillaes, as specified inthis 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 theyReg 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.

Question 5

Thanks Tristan for your comments. I will look into it and see how to apply them to my program. Thanks.

Kai 513 bronze badges · Answer 1 · 2022-03-11 08:14:04Z

Simply use theGreaterThan 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);       }

I've edited your question and answer to match the Q&A format. Nice job on getting your answer and +1 for having posted it!

Tristan Nemoz♦ 8,8793 gold badges11 silver badges39 bronze badges · Answer 2 · 2022-03-10 09:07:58Z

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

FliptargetReg to$|1\rangle$ ifx2Reg$>$yReg
Apply a$Z$ gate ontargetReg, which will phase-flip the states we're interested in
FliptargetReg to$|0\rangle$ ifx2Reg$>$yReg to disentangletargetReg 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 thetargetReg qubit as ancillaes, as specified inthis 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 theyReg 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.

Thanks Tristan for your comments. I will look into it and see how to apply them to my program. Thanks.

Movatterモバイル変換

Stack Exchange Network

Implementing the Oracle in Grover

2 Answers2

Your Answer

Sign up orlog in

Post as a guest

Linked

Related

Hot Network Questions

Subscribe to RSS