Logically, what does the second reflection in Grover's algorithm do? I currently don't have a lot of background in linear algebra so I'm failing to understand what exactly its purpose is and what it does.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
An application of the reflection operator change each amplitude of a basis state $ |i\rangle$ by $$ \alpha_i \rightarrow- \alpha_i + 2 \langle\alpha\rangle\ $$ where $ \langle\alpha\rangle\ $ is the average of all amplitudes. It follows the oracle which is use to "mark" the seeked elements $ |i\rangle$.
Say for instance that you have 8 elements, so you work on 3 qubits and you want to output $ |011\rangle$ with high probability. At the beginning, each basis state has $\frac{1}{8}$ probability to be measured as their amplitude are $\frac{1}{\sqrt{8}}$. The oracle first will mark $ |011\rangle$, so its amplitude will be $-\frac{1}{\sqrt{8}} = -\frac{1}{2\sqrt{2}}$.
$$ \langle\alpha\rangle\ = \frac{1}{8} (7* \frac{1}{\sqrt{8}} - \frac{1}{\sqrt{8}}) = \frac{6}{8\sqrt{8}} = \frac{3}{8\sqrt{2}}$$
So the amplitude of $ |011\rangle$ after the reflection operator becomes $$ - (-\frac{1}{2\sqrt{2}}) + 2\langle\alpha\rangle\ = \frac{5}{4\sqrt{2}} $$ while others will have a new amplitude: $$ - (\frac{1}{2\sqrt{2}}) + 2*\frac{3}{8\sqrt{2}} = \frac{1}{4\sqrt{2}}$$
If you square those amplitudes, then $ |011\rangle$ has $\frac{25}{32} \approx 0.78 > \frac{1}{8}$ probability to be measured, while another state will have $\frac{1}{32}$ probability to be measured. You see the probability of the solution to be outputed increased while non-solutions less likely to be.
