# Grover search with different diffusion operators

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 $$$$-U_{S_j}|S_j\rangle_{w}=|w\rangle$$$$ 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. 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}$$

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: the tensor product formula can learn from here

• Can you explain you simplification of the equation $U_{S_2}U_{10}|S_1\rangle$ Aug 12 '20 at 21:58
• 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.
– kita
Aug 12 '20 at 23:31
• Yes exactly that was what i was asking. Aug 13 '20 at 7:34