2
$\begingroup$

I am trying to implement Grover's search using Qiskit. And I would like to create entangled states so I could search for the index of a specific value in a list. For example, if the third element in the list has value 7, then the corresponding state should be $|3\rangle|7\rangle$. One way to do that is to construct a particular circuit for each element after the hadamard transform but it seems to be hard. Is there an efficient way in Qiskit to do that so I will not need to construct the circuit for every element in the list? Thank you for your help!

$\endgroup$
3
  • $\begingroup$ Can you share the first way you mention to implement this? Or add more detail in what the function you want to implement needs to do. If I understood correctly, you want an oracle $O: |x\rangle |0\rangle \rightarrow |x\rangle |f(x)\rangle$, where $f(x)$ is the element of a list in index $x$. In this case, is the list a classical one or is it stored with something like qRAM? $\endgroup$
    – epelaaez
    Jun 16 at 2:25
  • $\begingroup$ Hi epelaaez! Thank you for your reply. I think you are right. I am trying to construct a oracle as you said. Once the oracle is constructed, I think we can combine Grover operator to it and search for the index of a specific value. I think the data is stored in a classical way, for example, a python list or dictionary. $\endgroup$
    – Slangevar
    Jun 16 at 2:35
  • $\begingroup$ Great @Slangevar, I've answered your question below, I had to modify the oracle a little bit to fit it with Grover's algorithm. Please let me know if you have any other doubt in a comment in that answer, I'll be glad to help. $\endgroup$
    – epelaaez
    Jun 16 at 4:28
1
$\begingroup$

Entanglement

As to how to create entangled states, the most easy way to do this is with the following circuit:

qc = QuantumCircuit(4)
qc.h(0)
qc.cx(0, 1)
qc.cx(1, 2)
qc.cx(2, 3)

enter image description here

This is an example for $n=4$, and you get the state $\frac{1}{\sqrt{2}}(|0\rangle^{\otimes 4} + |1\rangle^{\otimes 4})$; as confirmed by the statevector_simulator.

svsim = Aer.get_backend('statevector_simulator')
result = svsim.run(qc).result().get_counts()
Output: {'0000': 0.5, '1111': 0.5}

Of course, you can extend this circuit to any number of qubits and get $\frac{1}{\sqrt{2}}(|0\rangle^{\otimes n} + |1\rangle^{\otimes n})$. Now, this is not a efficient way of doing this since the number of CNOT gates is $n-1$, thus error on these gates plus decoherence time of the qubits on real devices will affect your state. However, this is the way to do it. For more information on this, check this answer and the GHZ state page on Wikipedia.

Oracle

Now for the oracle, you want to implement a unitary $U|x\rangle |0\rangle = |x\rangle |f(x)\rangle$ such that $f(x)$ is the element of a list/array at index $x$. However, for Grover's algorithm, we want to implement a unitary of one of the following two forms:

$$ U|x\rangle = \left\{ \begin{array}{ll} |x\rangle & \mbox{if } x\not=\omega \\ -|x\rangle & \mbox{if } x = \omega \end{array} \right. $$

where $\omega$ is the "winner" state. The other form is

$$ U|x\rangle = (-1)^{f(x)}|x\rangle. $$

In the case you are describing, it is pretty easy to construct the first type of oracle. Suppose that you want $|\omega\rangle = |7\rangle = |111\rangle$, where the last one is in binary. We just need to make

$$ U = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\ \end{bmatrix}. $$

This works because the column where the element is $-1$ corresponds to the $|111\rangle$ state. You can do the same unitary for any number, just set the element in the corresponding element to $-1$. To translate this unitary matrix into a circuit, check out this answer.

I believe that the unitary as you describe it is not very useful in Grover's algorithm, but the method described above should work out. Just access the index $x$ of the list, classicaly build the unitary matrix by setting the element of the appropiate column to $-1$, and finally translate the matrix into a Qiskit circuit.

$\endgroup$
3
  • $\begingroup$ Thank you for your detailed answer! I think I misunderstood the oracle you mentioned in the comment. My idea was inspired from the answer here. But as the author indicated, it is inefficient to construct the circuit for each element in the list. I think it is possible to write a loop to create entanglement between the index, for example, 1 and the data, for example, 6. But it is cumblesome. Therefore, I was wondering if there is a quicker way. $\endgroup$
    – Slangevar
    Jun 16 at 4:57
  • 1
    $\begingroup$ I think the implementation in this answer to the question you linked is the best one you can do. This is because you need to read the list and construct a circuit to encode the parameter into the second register as shown in that answer. $\endgroup$
    – epelaaez
    Jun 16 at 5:04
  • 1
    $\begingroup$ Check out this answer, it may help you understand how to use Grover’s on database search. $\endgroup$
    – epelaaez
    Jun 16 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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