Quantum Operator Approach

Understand how the Grover search algorithm achieves efficiency through amplitude manipulation.

We now show how to carry out those reflections formally using quantum operators. The geometry gives us a clue. The first step is reflection with respect to ψother|ψ_{other}⟩. This corresponds to changing the sign of the amplitude for all states that are perpendicular to ψother|ψ_{other}⟩, which is just w|w⟩ because we have defined ψother|ψ_{other}⟩ that way. So, the first step makes the amplitude of w|w⟩ negative and produces the superposition state s1|s_1⟩.

How do we find the part of s0|s_0⟩ that lies along w|w⟩? To find that component, we express the state vector s0|s_0⟩ as the sum of a part s0|s_0⟩_∥ parallel to w|w⟩ and a part s0|s_0⟩_⊥ perpendicular to w|w⟩ and, hence, parallel to ψother|ψ_{other}⟩:

s0=s0+s0=wws0 project  along w+ψother ψother s0 projectalongψother .\left|s_0\right\rangle=\left|s_0\right\rangle_{\|}+\left|s_0\right\rangle_{\perp}=|w\rangle \underbrace{\left\langle w \mid s_0\right\rangle}_{\begin{array}{c} \hspace{0.1cm}\text { project } \\ \text { along }|w\rangle \end{array}}+\left|\psi_{\text {other }}\right\rangle \underbrace{\left\langle\psi_{\text {other }} \mid s_0\right\rangle}_{\begin{array}{c} \text { project} \\ \text {along}\left|\psi_{\text {other }}\right\rangle \end{array}} .

To understand the above equation, recall that the Dirac bracket ws0\left\langle w \mid s_0\right\rangle expresses the projection of the state vector s0\left|s_0\right\rangle along the direction of the state vector w|w\rangle. Then, all we need to do is change the sign of the part that is parallel to our desired state. This gives s1\left|s_1\right\rangle :

s1=wws0+ψother ψother s0.\left|s_1\right\rangle=-|w\rangle\left\langle w \mid s_0\right\rangle+\left|\psi_{\text {other }}\right\rangle\left\langle\psi_{\text {other }} \mid s_0\right\rangle.

Get hands-on with 1400+ tech skills courses.