Exercise 6.3

Consider two orthonormal states \(|\alpha\rangle\) and \(|\beta\rangle\) defined as

(1)\[\begin{split} \begin{split} |\alpha\rangle &= \frac{1}{\sqrt{N-M}}\sum_{x}'' |x\rangle \\ |\beta\rangle &= \frac{1}{\sqrt{M}}\sum_{x}' |x\rangle \\ \end{split} \end{split}\]

The equal superposition state can be rewritten under the basis \(\{|\alpha\rangle, |\beta\rangle\}\),

(2)\[ |\psi\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle = \sqrt{\frac{N-M}{N}}|\alpha\rangle + \sqrt{\frac{M}{N}}|\beta\rangle \]

Let

(3)\[ \cos\frac{\theta}{2} =\sqrt{\frac{N-M}{N}}, \sin\frac{\theta}{2} =\sqrt{\frac{M}{N}} \]

such that

(4)\[ \sin\theta =2\cos\frac{\theta}{2} \sin\frac{\theta}{2} =\frac{2\sqrt{M(N-M)}}{N} \]

Using eq. (3), eq. (2) becomes

(5)\[ |\psi\rangle = \cos\frac{\theta}{2} |\alpha\rangle + \sin\frac{\theta}{2} |\beta\rangle \]

The main text tells a Grover iteration takes \(|\psi\rangle\) to

(6)\[ G|\psi\rangle = \cos\frac{3\theta}{2}|\alpha \rangle + \sin\frac{3\theta}{2}|\beta\rangle \]

Using trigonometry identities to rewrite \(\cos({3\theta}/{2})\) and \(\sin({3\theta}/{2})\), \(G|\psi\rangle\) becomes

(7)\[\begin{split} \begin{split} G|\psi\rangle =& \left(\cos\theta \cos\frac{\theta}{2} - \sin\theta\sin\frac{\theta}{2}\right)|\alpha \rangle \\ &+ \left(\sin\theta \cos\frac{\theta}{2} + \cos\theta\sin\frac{\theta}{2}\right)|\beta\rangle \end{split} \end{split}\]

Above equation can also be re-written into below matrix form under basis \(\{|\alpha\rangle, |\beta\rangle\}\),

(8)\[\begin{split} G|\psi\rangle = \begin{pmatrix} \cos\theta \cos\frac{\theta}{2} - \sin\theta\sin\frac{\theta}{2} \\ \sin\theta \cos\frac{\theta}{2} + \cos\theta\sin\frac{\theta}{2} \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}\begin{pmatrix} \cos\frac{\theta}{2} \\ \sin\frac{\theta}{2} \end{pmatrix} \end{split}\]

Therefore, we may write the Grover iteration under basis \(\{|\alpha\rangle, |\beta\rangle\}\) as

(9)\[\begin{split} G|\psi\rangle = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} \end{split}\]