4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.