I was reading about the Grover Search algorithm on https://qiskit.org/textbook/ch-algorithms/grover.html#example. I understood the method but I have a few questions. My question regards the two-qubit case.

Does the diffusion operator $D=2|s\rangle\langle s|-1$, depend upon the initial state i.e $|+\rangle|+\rangle$ and the marked state?

Actually I was reading an article https://journals.aps.org/pra/pdf/10.1103/PhysRevA.68.022306, which had an equation \begin{equation} -U_{S_j}|S_j\rangle_{w}=|w\rangle \end{equation} with $U_x=1-2|x\rangle\langle x|$, $S_1=\left(\dfrac{0+1}{\sqrt{2}}\right)^{\otimes 2}$, and $w$ is the marked state. The other $S_{j's}$ can be the states for instance $|+\rangle|-\rangle$, $|-\rangle|-\rangle$, $|-\rangle|+\rangle$ etc. with total such $S_j$ being $16$. My question is how does one make the diffusion operator for a state $|+\rangle|-\rangle$. As an example from the table in the article it states for instance if $j=2$, $S_2=|+\rangle|-\rangle$ $$-U_{S_2}|S_1\rangle_{10}=-|00\rangle,$$ where $10=w$ is the marked state. Can somebody explain how this equation came? can somebody atleast hint at some references?


1 Answer 1

  1. it should be clear that the core of the Grover algorithm includes 3 steps

    a) prepare initial state $|s\rangle$

    b) apply $U=1-2|\omega\rangle\langle \omega|$

    c) apply $D=2|s\rangle\langle s|-1$

    then repeat step b and c

  2. In the original Grover algorithm, the diffusion operator is fixed as $D=2|s\rangle\langle s|-1$, which you can say it depends upon the initial state. Actually in the image of qiskit textbook, you can see the initial state is $|s\rangle=H^{\otimes n}|0\rangle^{n}$ enter image description here

  3. In the paper your reference, it extends the Grover algorithm, especially extends the diffusion operator from $|s\rangle$ (named as $\left|S_{1}\right\rangle$) to another 15 states $\left|S_{j}\right\rangle$

  4. For the equation you mentioned in the case of $j = 2$, the detail derivation is as follows: enter image description here the tensor product formula can learn from here

  • $\begingroup$ Can you explain you simplification of the equation $U_{S_2}U_{10}|S_1\rangle$ $\endgroup$
    – Upstart
    Aug 12, 2020 at 21:58
  • $\begingroup$ yes, it's a little bit complicate so I ignore some middle derivations. Basically you can follow my handwritten, to plugin the $U_{S_{2}}$ and $U_{10}$ of the first row into the equation. The tricky part is how to get the last 3 rows, you can use that tensor product formula, shrink it one by one. $\endgroup$
    – kita
    Aug 12, 2020 at 23:31
  • $\begingroup$ Yes exactly that was what i was asking. $\endgroup$
    – Upstart
    Aug 13, 2020 at 7:34

Your Answer

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

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