Writing Grover's Iterator in different computational phase [duplicate]

Question

This question is from Nielson and Chuang's Quantum Computation and Quantum Information:

Here $|\alpha\rangle$ is given by: $$\frac{1}{\sqrt{N-M}}\sum_{x} "|x\rangle $$ where $\sum_{x}" |x\rangle$ is the sum of states which are not the solution.

and $|\beta\rangle $ is given by: $$ \frac{1}{\sqrt{M}}\sum_{x} ' |x\rangle $$ where it represents all $M$ solutions.

$\theta$ is defined by: $$\cos\Big(\frac{\theta}{2}\Big) = \sqrt{\frac {N-M}{N}}$$

I understand everything mentioned above as well as the further geometric visualization. However, I am having trouble trying to come up with a justified way to solve this exercise. The only thing that I understand is that $G$ must be a unitary Matrix made up of trigonometric functions. How can I approach this problem?

Answer 1

You can rewrite $|\psi\rangle$ in terms of $\alpha$ and $\beta$ i.e. $$ |\psi\rangle = \cos(\theta/2)|\alpha\rangle + \sin(\theta/2)|\beta\rangle $$ Also, G rotates the state vector by $\theta$ towards $\beta$. $$ G|\psi\rangle = \cos(3\theta/2)|\alpha\rangle + \sin(3\theta/2)|\beta\rangle $$ $$ \begin{bmatrix} x_{11} & x_{12}\\ x_{21} & x_{22}\\ \end{bmatrix} \begin{bmatrix} \cos(\theta/2)\\ \sin(\theta/2)\\ \end{bmatrix} = \begin{bmatrix} \cos(3\theta/2)\\ \sin(3\theta/2)\\ \end{bmatrix} = \begin{bmatrix} \cos(\theta)\cos(\theta/2)-\sin(\theta)\sin(\theta/2)\\ \sin(\theta)\cos(\theta/2)+\cos(\theta)\sin(\theta/2)\\ \end{bmatrix} $$ By comparison, you can find the value of $x_{11},x_{12},x_{21}$ and $x_{22}$, and hence, G which comes out to be $$ \begin{bmatrix} \cos(\theta) && -\sin(\theta)\\ \sin(\theta) && \cos(\theta)\\ \end{bmatrix} $$