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.

New contributor
At2005 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\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.

$\endgroup$

Your Answer

At2005 is a new contributor. Be nice, and check out our Code of Conduct.

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.