#### Problem:
We have a function $f(x)$ and there is a speical key $w$ where $f(w) = 1$ while for other input $x$, $f(x)=0$. How to find that $w$.
#### Solution
1. Design an oracle
$$
U(\ket{x-}) = \begin{cases}
\ket{x-} & \text{if $x\ne w$} \\
-\ket{x-} & \text{if $x=w$}
\end{cases}
$$
2. Create superpostion and apply the oracle to it (to traverse all cases)
$$
\begin{align*}
U(\ket{+}^{\otimes n}\otimes\ket{-})
&= \sum_x{U(\ket{x-})} \\
&= \left(\sum_{x\ne w}\ket{x-}\right)-\ket{w-} \\
&= (\left(\sum_{x\ne w}\ket{x}\right)-\ket{w})\otimes \ket{-}
\end{align*}
$$
3. Amplitude Amplification
Although we flip the phase of the target state $\ket{w}$ to $-1$, it's amplitude is still the same ( $\frac{1}{2^n}$ ). We will apply a diffuser operator $U_s$ so that the amplitude of $\ket{w}$ will increase a little bit (the amplitude of other states will decrease).
Repeating step 2 and 3 for around $\frac{\pi}{4}\sqrt{N}$ times, the amplitude of $\ket{w}$ will be the max and when we measure, it's highly possible that we will get $\ket{w}$ rather than other states:
| Iteration | Step | Amp of Winner ( $\ket{111}$ ) | Amp of Rest ( $\ket{x \neq 111}$ ) | Mean ( $\mu$ ) | System State $\ket{\psi}$ (approx.) | Probability of Winner |
| :--: | :--: | :--: | :--: | :--: | :--: | :--: |
| Start | Init ( $H^{\otimes 3}$ ) | 0.354 ( $+$ ) | 0.354 ( $+$ ) | 0.354 | $\sum_{i=0}^7 0.354\ket{i}$ | $12.5\%$ |
| **Iter 1** | Oracle ( $U_f$ ) | -0.354 ( $-$ ) | 0.354 ( $+$ ) | 0.265 | $-0.354\ket{w} + \sum 0.354\ket{s'}$ | $12.5\%$ |
| | Diffuser ( $U_s$ ) | 0.884 ( $+$ ) | 0.176 ( $+$ ) | | $0.884\ket{w} + \sum 0.176\ket{s'}$ | 78.1% |
| **Iter 2** | Oracle ( $U_f$ ) | -0.884 ( $-$ ) | 0.176 ( $+$ ) | 0.044 | $-0.884\ket{w} + \sum 0.176\ket{s'}$ | $78.1\%$ |
| | Diffuser ( $U_s$ ) | 0.972 ( $+$ ) | -0.088 ( $-$ ) | | $0.972\ket{w} - \sum 0.088\ket{s'}$ | 94.5% (best) |
| **Iter 3** | Oracle ( $U_f$ ) | -0.972 ( $-$ ) | -0.088 ( $-$ ) | -0.199 | $-0.972\ket{w} - \sum 0.088\ket{s'}$ | $94.5\%$ |
| | Diffuser ( $U_s$ ) | 0.574 ( $+$ ) | -0.309 ( $-$ ) | | $0.574\ket{w} - \sum 0.309\ket{s'}$ | 32.9% (worse) |
#### Details
##### Diffuser operator:
$$U_s = 2|s\rangle\langle s| - I$$
. In gemotry, it will reflect the input using $\ket{s}$ as the axis.
In other words, $\ket{x}$ and $U_s(\ket{x})$ are axisymmetric w.r.t. $\ket{s}$.
Any vector $\ket{\psi}$ can be written as sum of two components:
* $\ket{\psi_{\parallel}} = c \cdot \ket{s}$: component that is parallel to $\ket{s}$
* $$\frac{U_s(\ket{\psi_{\parallel}})}{c} = U_s |s\rangle = (2|s\rangle\langle s| - I) |s\rangle = 2|s\rangle(\langle s|s\rangle) - |s\rangle = 2|s\rangle(1) - |s\rangle = |s\rangle$$
* $\ket{\psi_{\perp}}$: component that is othogonal to $\ket{s}$
* $$U_s |\psi_{\perp}\rangle = (2|s\rangle\langle s| - I) |\psi_{\perp}\rangle = 2|s\rangle(\langle s|\psi_{\perp}\rangle) - |\psi_{\perp}\rangle = 0 - |\psi_{\perp}\rangle = - |\psi_{\perp}\rangle$$
So $U_s(\ket{\psi}) = U_s(\ket{\psi_\parallel}) + U_s(\ket{\psi_{\perp}}) = \ket{\psi_{\parallel}-\psi_\perp}$, which is a flip of $\ket{\psi}$ w.r.t. $\ket{s}$.
##### Flip Axis:
In the problem, we will set the axis $\ket{s}$ as the average state:
$$|s\rangle = H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$
##### The Geometry Breakdown:
Rather than discussing a $2^n$ dimension space, we can project it to a 2-d space with two axes:
* $\ket{w}$: the target state
* $\ket{s'}$: average of all non-target states: $|s'\rangle = \frac{1}{\sqrt{N-1}} \sum_{x \neq w} |x\rangle$
The flip-axis $\ket{s}$ is close to axis $\ket{s'}$
$$
\begin{align*}
|s\rangle &= \sqrt{\frac{1}{N}} |w\rangle + \sqrt{\frac{N-1}{N}} |s'\rangle \\
&= \sin(\frac{\theta}{2}) |w\rangle + \cos(\frac{\theta}{2}) |s'\rangle
\end{align*}
$$
, where we denote $\sin(\frac{\theta}{2}) = \frac{1}{\sqrt{N}}$. Usually N is large ( $2^n$ ) and $\frac{\theta}{2}= \frac{1}{\sqrt{N}}$.
##### Two flips make one rotation:
* Oracle: flip state w.r.t. $\ket{s'}$ (the phase of $\ket{w}$ is reverted).
* $U_s$: flip state w.r.t. $\ket{s}$.
Reflection twice == one rotation with angle that's two times of the axes ( $\ket{s}$ and $\ket{s'}$ , i.e. $\frac{\theta}{2}$ ). Beginning with $\frac{\theta}{2}$, after one rotation is $\frac{3\theta}{2}$, after second rotation is $\frac{5\theta}{2}$... To rotate to $\frac{\pi}{2}$ ( $\ket{w}$ axis), we need $\frac{\pi/2}{\theta} \approx \frac{\pi}{4}\sqrt{N}$ times.
A visualization created by gemini:https://ai.studio/apps/drive/1RgfwgxwlHwugx1Umh32SloO2Dy16ogZO
##### Circuit for diffusion operator:
We can rewrite $U_s$ as
$$
\begin{align*}
U_s &= 2|s\rangle\langle s| - I \\
&= U_s = 2 (H^{\otimes n} |0\rangle\langle 0| H^{\otimes n}) - I \\
&= H^{\otimes n} (2|0\rangle\langle 0| - I) H^{\otimes n}
\end{align*}
$$
So we convert $U_s$ to $H$ gate, $U_0$ then another $H$ gate. $U_0$ is a flip w.r.t. $\ket{0}$, we can use Multi-Controlled Z gate to achieve it (with some tricks).
#### Takeaways:
* Achieve the goal gradually (by amplifying the prob of the answer).
* Beauty of linear algebra.
#### Follow-ups:
* What if there are $M$ (more than one) targets?
* We need to iterate $k \approx \frac{\pi}{4}\sqrt{N/M}$ times.
* However, when M is unknown, we need to use [Quantum Counting Algorithm](https://en.wikipedia.org/wiki/Quantum_counting_algorithm) to estimate M.
* Can we do better than $O(\sqrt(N))$?
* No. The lowerbound is $\Omega(\sqrt{N})$ in QC (BBBV Theorem).