Grover's Search & Amplitude Amplification

1. 1
   Step 1:

   $$H^{\otimes n}\big(2\lvert0^n\rangle\langle0^n\rvert-I\big)H^{\otimes n}=2\big(H^{\otimes n}\lvert0^n\rangle\big)\big(\langle0^n\rvert H^{\otimes n}\big)-H^{\otimes n}H^{\otimes n}$$

   Distribute the product over the difference.
2. 2
   Step 2:

   $$=2\lvert s\rangle\langle s\rvert-I=D$$

   $H^{\otimes n}\lvert0^n\rangle=\lvert s\rangle$, $(H^{\otimes n})^\dagger=H^{\otimes n}$ so $\langle0^n\rvert H^{\otimes n}=\langle s\rvert$, and $H^2=I$ on every qubit.
3. 3
   Step 3:

   $$X^{\otimes n}\lvert1^n\rangle=\lvert0^n\rangle\ \Rightarrow\ X^{\otimes n}\big(I-2\lvert1^n\rangle\langle1^n\rvert\big)X^{\otimes n}=I-2\lvert0^n\rangle\langle0^n\rvert$$

   $X^{\otimes n}$ is self-inverse and maps the all-ones string to the all-zeros string, so conjugation moves the projector.
4. 4
   Step 4:

   $$I-2\lvert0^n\rangle\langle0^n\rvert=-\big(2\lvert0^n\rangle\langle0^n\rvert-I\big)$$

   Factor out $-1$.
5. 5
   Step 5:

   $$H^{\otimes n}X^{\otimes n}(C^{n-1}Z)X^{\otimes n}H^{\otimes n}=-H^{\otimes n}\big(2\lvert0^n\rangle\langle0^n\rvert-I\big)H^{\otimes n}=-D$$

   Combine the previous three lines.

∎

1. 1
   Step 1:

   $$O\lvert\alpha\rangle=\lvert\alpha\rangle,\qquad O\lvert\beta\rangle=-\lvert\beta\rangle$$

   $\lvert\alpha\rangle$ only contains unmarked $x$ (sign $+1$), $\lvert\beta\rangle$ only marked $x$ (sign $-1$). So $O$ maps $\mathcal P$ into itself and acts there as $2\lvert\alpha\rangle\langle\alpha\rvert-I_{\mathcal P}$.
2. 2
   Step 2:

   $$D\lvert v\rangle=2\langle s\vert v\rangle\lvert s\rangle-\lvert v\rangle\in\mathcal P\quad\forall\,\lvert v\rangle\in\mathcal P$$

   $\lvert s\rangle\in\mathcal P$; on $\mathcal P$ the operator $D$ is $2\lvert s\rangle\langle s\rvert-I_{\mathcal P}$, the reflection about $\lvert s\rangle$.
3. 3
   Step 3:

   $$R_\phi:=2\lvert u_\phi\rangle\langle u_\phi\rvert-I=\begin{pmatrix}\cos2\phi&\sin2\phi\\\sin2\phi&-\cos2\phi\end{pmatrix},\quad\lvert u_\phi\rangle=\cos\phi\lvert\alpha\rangle+\sin\phi\lvert\beta\rangle$$

   In the basis $(\lvert\alpha\rangle,\lvert\beta\rangle)$: $2\lvert u_\phi\rangle\langle u_\phi\rvert=\begin{pmatrix}2\cos^2\phi&2\sin\phi\cos\phi\\2\sin\phi\cos\phi&2\sin^2\phi\end{pmatrix}$, then use the double-angle formulas.
4. 4
   Step 4:

   $$O=R_0,\qquad D=R_\theta$$

   $\lvert\alpha\rangle=\lvert u_0\rangle$ and $\lvert s\rangle=\lvert u_\theta\rangle$.
5. 5
   Step 5:

   $$R_\theta R_0=\begin{pmatrix}\cos2\theta&\sin2\theta\\\sin2\theta&-\cos2\theta\end{pmatrix}\begin{pmatrix}1&0\\0&-1\end{pmatrix}=\begin{pmatrix}\cos2\theta&-\sin2\theta\\\sin2\theta&\cos2\theta\end{pmatrix}$$

   Matrix multiplication: the second column is negated. The result is the rotation matrix by angle $2\theta$.
6. 6
   Step 6:

   $$G^k\lvert u_\theta\rangle=\lvert u_{\theta+2k\theta}\rangle=\cos\big((2k+1)\theta\big)\lvert\alpha\rangle+\sin\big((2k+1)\theta\big)\lvert\beta\rangle$$

   Rotations compose by adding angles and $\lvert s\rangle=\lvert u_\theta\rangle$.
7. 7
   Step 7:

   $$P_k=\sum_{w\in M}\lvert\langle w\vert G^k\vert s\rangle\rvert^2=\sin^2\big((2k+1)\theta\big)\sum_{w\in M}\frac1M=\sin^2\big((2k+1)\theta\big)$$

   Born rule: $\langle w\vert\alpha\rangle=0$ and $\langle w\vert\beta\rangle=1/\sqrt M$ for $w\in M$.

∎

1. 1
   Step 1:

   $$(2k+1)\theta=\frac\pi2\iff k=\frac{\pi}{4\theta}-\frac12$$

   The amplitude $\sin((2k+1)\theta)$ is $1$ exactly when the angle is $\pi/2$; this real $k$ is in general not an integer.
2. 2
   Step 2:

   $$\frac\pi{4\theta}-1<k^\ast\le\frac\pi{4\theta}\ \Rightarrow\ \Big\lvert k^\ast-\Big(\frac\pi{4\theta}-\frac12\Big)\Big\rvert\le\frac12$$

   Definition of the floor function.
3. 3
   Step 3:

   $$\Big\lvert(2k^\ast+1)\theta-\frac\pi2\Big\rvert=2\theta\,\Big\lvert k^\ast-\Big(\frac\pi{4\theta}-\frac12\Big)\Big\rvert\le\theta$$

   Multiply the previous inequality by $2\theta$.
4. 4
   Step 4:

   $$P_{k^\ast}=\cos^2\Big((2k^\ast+1)\theta-\frac\pi2\Big)\ge\cos^2\theta=1-\sin^2\theta=1-\frac MN$$

   $\sin x=\cos(x-\pi/2)$ and $\cos^2$ is decreasing in $\lvert y\rvert$ on $[0,\tfrac\pi2]$, with $\lvert y\rvert\le\theta<\tfrac\pi2$.
5. 5
   Step 5:

   $$\theta\ge\sin\theta=\sqrt{\frac MN}\ \Rightarrow\ k^\ast\le\frac\pi{4\theta}\le\frac\pi4\sqrt{\frac NM}$$

   $\sin\theta\le\theta$ for $\theta\ge0$. For $M\ll N$, $\theta\approx\sin\theta$ and the bound is tight: $k^\ast\approx\tfrac\pi4\sqrt{N/M}$.

∎

1. 1
   Step 1:

   $$D_k:=\sum_x\big\lVert\psi^x_k-\psi_k\big\rVert^2$$

   Hybrid quantity (Nielsen–Chuang §6.6): total squared distance between the run with oracle $O_x$ and the oracle-free run after $k$ steps.
2. 2
   Step 2:

   $$\psi^x_{k+1}-\psi_{k+1}=U_{k+1}\big(O_x\psi^x_k-\psi_k\big)=U_{k+1}\big(O_x(\psi^x_k-\psi_k)+(O_x-I)\psi_k\big)$$

   Add and subtract $O_x\psi_k$.
3. 3
   Step 3:

   $$\big\lVert\psi^x_{k+1}-\psi_{k+1}\big\rVert\le\big\lVert\psi^x_k-\psi_k\big\rVert+2\big\lvert\alpha_{k,x}\big\rvert,\qquad\lvert\alpha_{k,x}\rvert:=\big\lVert(\langle x\rvert\otimes I)\psi_k\big\rVert$$

   Unitaries preserve norms, triangle inequality, and $(O_x-I)\psi_k=-2(\lvert x\rangle\langle x\rvert\otimes I)\psi_k$.
4. 4
   Step 4:

   $$D_{k+1}\le\sum_x\Big(\lVert\psi^x_k-\psi_k\rVert^2+4\lVert\psi^x_k-\psi_k\rVert\lvert\alpha_{k,x}\rvert+4\lvert\alpha_{k,x}\rvert^2\Big)$$

   Square the previous line and sum over $x$.
5. 5
   Step 5:

   $$\sum_x\lVert\psi^x_k-\psi_k\rVert\lvert\alpha_{k,x}\rvert\le\sqrt{D_k}\sqrt{\textstyle\sum_x\lvert\alpha_{k,x}\rvert^2}=\sqrt{D_k},\qquad\textstyle\sum_x\lvert\alpha_{k,x}\rvert^2=\lVert\psi_k\rVert^2=1$$

   Cauchy–Schwarz; the $\lvert\alpha_{k,x}\rvert^2$ are the index-register probabilities of a normalised state.
6. 6
   Step 6:

   $$D_{k+1}\le D_k+4\sqrt{D_k}+4=\big(\sqrt{D_k}+2\big)^2\ \Rightarrow\ \sqrt{D_{k+1}}\le\sqrt{D_k}+2$$

   Insert into the previous bound and take square roots.
7. 7
   Step 7:

   $$D_0=0\ \Rightarrow\ D_T\le4T^2$$

   Induction on $k$: $\sqrt{D_k}\le2k$.
8. 8
   Step 8:

   $$E_x:=\big\lVert\psi^x_T-\lvert x\rangle\otimes\lvert\omega_x\rangle\big\rVert^2=2-2\,\mathrm{Re}\langle x,\omega_x\vert\psi^x_T\rangle\le2-2\sqrt{\tfrac12}$$

   Choose the workspace state $\lvert\omega_x\rangle$ and a global phase so that $\langle x,\omega_x\vert\psi^x_T\rangle=\lVert(\langle x\rvert\otimes I)\psi^x_T\rVert\ge\sqrt{1/2}$ (success probability at least $\tfrac12$).
9. 9
   Step 9:

   $$F_x:=\big\lVert\psi_T-\lvert x\rangle\lvert\omega_x\rangle\big\rVert^2,\qquad\sum_xF_x\ge2N-2\sqrt N$$

   $F_x=2-2\mathrm{Re}\langle x,\omega_x\vert\psi_T\rangle$ and $\sum_x\lvert\langle x,\omega_x\vert\psi_T\rangle\rvert\le\sqrt N\sqrt{\sum_x\lVert(\langle x\rvert\otimes I)\psi_T\rVert^2}=\sqrt N$ by Cauchy–Schwarz.
10. 10
    Step 10:

    $$D_T=\sum_x\lVert(\psi^x_T-\lvert x\rangle\lvert\omega_x\rangle)-(\psi_T-\lvert x\rangle\lvert\omega_x\rangle)\rVert^2\ge\sum_x\big(\sqrt{F_x}-\sqrt{E_x}\big)^2$$

    Reverse triangle inequality $\lVert a-b\rVert\ge\lVert b\rVert-\lVert a\rVert$.
11. 11
    Step 11:

    $$\sum_x\big(\sqrt{F_x}-\sqrt{E_x}\big)^2\ge\sum_xF_x-2\sqrt{\textstyle\sum_xF_x}\sqrt{\textstyle\sum_xE_x}+\sum_xE_x$$

    Expand and apply Cauchy–Schwarz to the cross term $\sum_x\sqrt{F_xE_x}$.
12. 12
    Step 12:

    $$D_T\ge\Big(\sqrt{\textstyle\sum_xF_x}-\sqrt{\textstyle\sum_xE_x}\Big)^2\ge\Big(\sqrt{2N-2\sqrt N}-\sqrt{(2-\sqrt2)N}\Big)^2=c_NN$$

    $\sum_xE_x\le(2-\sqrt2)N$ and $\sum_xF_x\ge2N-2\sqrt N$ (valid once $2N-2\sqrt N\ge(2-\sqrt2)N$, i.e. $N\ge2$); as $N\to\infty$, $c_N\to(\sqrt2-\sqrt{2-\sqrt2})^2\approx0.42>0$.
13. 13
    Step 13:

    $$4T^2\ge D_T\ge c_NN\ \Rightarrow\ T\ge\frac{\sqrt{c_N}}{2}\sqrt N=\Omega(\sqrt N)$$

    Combine the upper and lower bounds on $D_T$. Grover's $\tfrac\pi4\sqrt N$ is therefore optimal up to a constant factor.

∎

1. 1
   Step 1:

   $$S_\chi\big\vert_{\mathcal P}=2\lvert\psi_0\rangle\langle\psi_0\rvert-I_{\mathcal P},\qquad\mathcal P=\mathrm{span}\{\lvert\psi_0\rangle,\lvert\psi_1\rangle\}$$

   $S_\chi\lvert\psi_0\rangle=\lvert\psi_0\rangle$ and $S_\chi\lvert\psi_1\rangle=-\lvert\psi_1\rangle$, exactly as for $O$.
2. 2
   Step 2:

   $$-AS_0A^{-1}=A\big(2\lvert0\rangle\langle0\rvert-I\big)A^{-1}=2\,A\lvert0\rangle\langle0\rvert A^\dagger-I=2\lvert\Psi\rangle\langle\Psi\rvert-I$$

   $A^{-1}=A^\dagger$ and $\lvert\Psi\rangle:=A\lvert0\rangle$; this is the reflection about $\lvert\Psi\rangle\in\mathcal P$, which maps $\mathcal P$ to itself.
3. 3
   Step 3:

   $$Q\big\vert_{\mathcal P}=R_{\theta_a}R_0=\begin{pmatrix}\cos2\theta_a&-\sin2\theta_a\\\sin2\theta_a&\cos2\theta_a\end{pmatrix}$$

   Same computation as for Grover with $\lvert\alpha\rangle\to\lvert\psi_0\rangle$, $\lvert\beta\rangle\to\lvert\psi_1\rangle$, $\theta\to\theta_a$.
4. 4
   Step 4:

   $$Q^kA\lvert0\rangle=\cos\big((2k+1)\theta_a\big)\lvert\psi_0\rangle+\sin\big((2k+1)\theta_a\big)\lvert\psi_1\rangle$$

   Rotation by $2k\theta_a$ of the angle-$\theta_a$ vector $\lvert\Psi\rangle$.
5. 5
   Step 5:

   $$A=H^{\otimes n},\ \chi=f\ \Rightarrow\ \sin^2\theta_a=\frac MN,\ S_\chi=O,\ Q=-H^{\otimes n}S_0H^{\otimes n}O=DO$$

   Grover search is the special case $A=H^{\otimes n}$, and the success bound follows from the optimal-$k$ theorem with $M/N$ replaced by $a$.

∎