3
$\begingroup$

When interpreted geometrically, the second phase of the Grover's algorithm which corresponds to inversion about the mean is interpreted as reflection over the original state.

Can you explain intuitively the relationship between those two?

$\endgroup$
4
$\begingroup$

The Grover diffusion operator, the second phase of the algorithm, is given by:

$$D = 2\left|s\right>\left<s\right| - I$$

where $\left|s\right> = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\left|x\right>$, which is also known as the uniform superposition, or, in the case of the question, the "original state". To see why this inverts over the mean, first notice that, for a given state $\left|\psi\right> = \sum_{x=0}^{N-1}a_x \left|x\right>$:

$$\left|s\right>\langle s|\psi\rangle = (\frac{1}{N}\sum_{x=0}^{N-1}a_x)\sum_{x=0}^{N-1}\left|x\right>$$

Thus, $(2\left|s\right>\left<s\right| - I)\left|\psi\right> = 2\left|s\right>\langle s|\psi\rangle - \left|\psi\right>$, for the probability amplitude for each $\left|x\right>$, gives double the mean value of all the probability amplitudes minus the original amplitude: inversion over the mean.

$D$'s basic 2 projection minus identity structure is what makes it interpretable as a reflection over $\left|s\right>$: to see this intuitively, notice that if $\left|\psi\right> = a_s \left|s\right> + a_r \left|r\right>$ where $\langle s|r\rangle = 0$ ($s$ and $r$ are orthogonal), then $D\left|\psi\right> = 2a_s \left|s\right> - a_s\left|s\right> - a_r \left|r\right> = a_s \left|s\right> - a_r \left|r\right>$.

The first phase is also a reflection too in a slightly different manner. To negate only the target vector $\left|\omega\right>$, the operator is of the form $I - 2\left|\omega\right>\left<\omega\right|$: the probability amplitude of states orthogonal to $\left|\omega\right>$ is left alone while the probability amplitude of $\left|\omega\right>$ is negated. This reversal means that, instead of being a reflection over $\left|\omega\right>$, it is a reflection over the hyperplane orthogonal to $\left|\omega\right>$.

You can interpret both reflections together by creating a plane out of the orthogonal $\left|\omega\right>$ and $\left|s'\right> = \frac{1}{\sqrt{N - 1}} \sum_{x\neq\omega}\left|x\right>$ (Wikipedia's diagram of this is excellent). Then the first phase is a reflection over $\left|s'\right>$ and the second phase is a reflection over $\left|s\right>$. Since $\left|s\right>$ is at an angle away from $\left|s'\right>$ towards $\left|\omega\right>$, then successive applications of the first and second phase will steer the state towards $\left|\omega\right>$. Using this reflection paradigm, you can with some effort derive the approximately $\frac{\pi}{4} \sqrt{N}$ stopping point before the reflecting goes too far.

$\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.