Grover's algorithm for the real problem of finding the index of an array element

Question

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 :

original image link

Answer 1

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