💼 Case: lets look back at Grover’s search algorithm except this time rather than finding a solution which leads to $f\{0,1\}^n=1$ here we try to find the number of solutions $M$
Starting from the matrix representation of the operator $G$ in the plane generated by $\ket{\sigma},\ket{\tau}$
$$ G_{\sigma,\tau}=\begin{bmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \quad \text{where} \quad \sin \theta/2 =\sqrt{M/N} $$
🗒️ Note: the eigenvalues are $e^{i\theta}$ and $e^{-i\theta}$ corresponding to the eigenvectors $\ket{a}=i\ket{\sigma}+\ket{\tau}$ and $\ket{b}=\ket{\sigma}+i\ket{\tau}$
We apply the phase estimation algorithm to determine the eigenvalues of $G_{\sigma, \tau}$ to get $M$
Do the first step of the phase estimation algorithm with $U=G_{\sigma,\tau}$
$$ \begin{aligned} \text{first register:} \quad t&=s+ \operatorname{ceil} \left [ \log \left ( 2+\frac{1}{2\epsilon} \right )\right ] \\ \text{second register:} \quad \ket{\psi}&=\frac{1}{\sqrt{N}} \sum ^{N-1}_{x=0} \ket{x}
\end{aligned} $$
which is a linear combination of $\ket{\sigma}$ and $\ket{\tau}$ so of $\ket{a}$ and $\ket{b}$
Measurement of the first register will provide with probability $1-\epsilon$ an approximation of $\theta$
$$ |\Delta \theta|\le 2^{-s} $$
which using $\sin \theta/2 =\sqrt{M/N}$ gives us an approximation for $M$
When $s$ is large we can approximate
$$ \frac{\text d M}{\text d \theta} \approx \sqrt{MN}\cos(\tfrac{\theta}{2}) $$
Hence if the phase estimation yields an error $|\Delta \theta|\le 2^{-s}$ the corresponding error in $M$
$$ |\Delta M |\le 2^{-s} \sqrt{MN} $$
💃 Example: lets set $s= \operatorname{ceil} (\frac n2)+1$ then with high probability our measurement of $\theta$ is within $2^{-s}$
💼 Case: lets look when $M=0$ or $M=1$