2

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

Exercise 6.3: Show that in the $\vert \alpha \rangle$, $\vert \beta \rangle$ basis, we may write the Grover iteration as
$$ G = \begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix}, \tag{6.13} $$

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?

Frederik vom Ende
  • 4,163
  • 3
  • 12
  • 49
MetaInformation
  • 577
  • 2
  • 15

1 Answers1

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} $$

viditjain08
  • 63
  • 3