2
$\begingroup$

Good day. I am interested in an IMPLEMENTED, not theoretical, example of code for solving the problem of finding the INDEX of an element in an uncorrected array using Grover's Algorithm. The task looks like this: there is an array [3,6,2,4,9,0,1,5] and it is necessary to determine the index of the element in this array, which is 9 (that is, the result should be 4). I fully understand the example of Grover's algorithm implementation here from qiskit https://qiskit.org/textbook/ch-algorithms/grover.html, but I cannot transform it to solve the real problem described above. It is desirable to present the solutions on qiskit in Python. P.S. I have seen these links, but this all does not provide clarity for me and understanding of how to implement this task: 1, 2, 3, 4. I would be very grateful for a detailed explanation.!

After first answer I have questions described in comments and this image : question

original image link

Improve this question
$\endgroup$
3
  • $\begingroup$ Could you please explain where is quantum computing used in this case? $\endgroup$
    – Maf
    Mar 28, 2021 at 12:13
  • $\begingroup$ @Maf I'm just starting to study this question, so I can't give you a qualified answer $\endgroup$
    – Sergey Ivanow
    Mar 30, 2021 at 19:30
  • $\begingroup$ Hi, I am currently working on same problem of a simple database search (like a text file with some entries) using Grover and came across your question. Do you have the source code with which you were able to solve this search prob? $\endgroup$
    – aneela
    Jul 28, 2022 at 6:51

1 Answer 1

Reset to default
4
$\begingroup$

In your case, the array would have to be inputed into the quantum circuit. Usually in Grover, this is let to the oracle who would have some access to it, or to a Quantum Random Access Memory (or QRAM) that would load it for you efficiently (but unfortunately it is not there yet).

What you would need in your case is 3 qubits for encoding indices (as you have an array of length 8 -- let's call them register 1) and you would need an extra 4 qubits (where you can have as bitstrings all integers between 0 and 16, as your maximum is 9 -- let's call them register 2). Also probably extra qubits for other operations like phase shift and your oracle.

So we can write as: $ | 0 \rangle_1 | 0 \rangle_2 | 0 \rangle_{extra} $. Applying Hadamard transform on register 1 will then give you: $ \sum_{i=0}^{7} | i \rangle_1 | 0 \rangle_2 | 0 \rangle_{extra} $

Of course, you want first an operator to load your array (assuming no code does it for you at the moment). You want to end up with the state: $$ \sum_{i=0}^{7} | i \rangle_1 | array(i) \rangle_2 | 0 \rangle_{extra} $$ where $array(i)$ corresponds to the $i$-th element.

Unefficiently, you have to loop over each index (represented by a bitstring in register 1) and apply a control operation that will load $array(i)$ represented by a bitstring in register 2. So a sequence of multi-controlled NOTs for bitstring loading. As an example, say you want to load the third element which is $2$ (and its index in the array is 2) and in bitstring $010$ with $3$ qubits or $0100$ with $4$ (or $0010$ in reverse order depending how you read). So your multi-control check in register 1 that the index is $010$ and apply a NOT gate such that the value in register 2 corresponds to element $2$ (the NOT will be on the second qubit of register 2 -- or the third in reverse order).

Finally, in your case you need to implement for Grover iterations, the operation that identify the element $9$. This is again a multi-controlled NOT where you control on register $2$ that the bitstring you look at is $9$ ($1001$) and the NOT will be on the phase shift qubit for Grover to mark that state.

Then with these operations, you do your Grover iterations as usual. I won't have code to show but figuring this out is a good exercise.

EDIT: Sorry I draw and write really bad... Drawing asked explaining a few steps

Improve this answer
$\endgroup$
12
  • $\begingroup$ Thanks! This part is not completely clear to me: "So your multi-control check in register 1 that the index is 010 and apply a NOT gate such that the value in register 2 corresponds to element 2 (the NOT will be on the second qubit of register 2 -- or the third in reverse order). Finally, in your case you need to implement for Grover iterations, the operation that identify the element 9. This is again a multi-controlled NOT where you control on register 2 that the bitstring you look at is 9 (1001) and the NOT will be on the phase shift qubit for Grover to mark that state." $\endgroup$
    – Sergey Ivanow
    Mar 25, 2021 at 19:10
  • $\begingroup$ I realized that I need to start 2 quantum registers. In one case, I will feed the Grover algorithm the values of the indices of the elements (or rather their super position, since I apply the Hadamard operator to all of them), and in the second case, I must also write the superposition of all the numbers from 0 to 16 (i.e. Also apply the Hadamard operator for all four qubits of the second register)? Need separate oracles for both checking case 1 and checking case 2? Or only for register 2? $\endgroup$
    – Sergey Ivanow
    Mar 25, 2021 at 19:11
  • $\begingroup$ And if there should be oracles for both registers, what should each of them check and what should happen after each of them checks? $\endgroup$
    – Sergey Ivanow
    Mar 25, 2021 at 19:11
  • $\begingroup$ See to image in edited question please. $\endgroup$
    – Sergey Ivanow
    Mar 25, 2021 at 19:37
  • 1
    $\begingroup$ +1. cnada is back! $\endgroup$
    – user1271772
    Mar 25, 2021 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.