Changing qubits coefficients to trigonometric functions in Grover Algorithm

We know that the Initial state $|psirangle$ can be represented as $sinfrac{theta}{2}|chirangle + cosfrac{theta}{2}|xirangle$.

We can prove the result $G^R|psirangle = sinfrac{(2R+1)theta}{2}|chirangle + cosfrac{(2R+1)theta}{2}|xirangle$ by Induction

Base Case

When $R=0$, $G^R=G^0=I$ and $2R+1=2times0+1=1$. Thus $G^0|psirangle = sinfrac{(2times 0+1)theta}{2}|chirangle + cosfrac{(2times 0+1)theta}{2}|xirangle = sinfrac{theta}{2}|chirangle + cosfrac{theta}{2}|xirangle = |psirangle$ is true. Base Case Proven

Inductive Step

Let us assume this is true for $forall R leq k$ i.e. $G^{k}|psirangle = sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle $

Induction Proof

Note: The math below is terse but not that complicated. However, it requires some prior knowledge of trigonmetry identities as well as Ket-Bra Algebra

First we will derive some useful results. From the same paper's Appendix B1 we are given that $G = UO = (H^{otimes n}(2|0ranglelangle0|-I)H^{otimes n})O$ where $O$ is the oracle.

We know that since all states in $|chirangle$ are marked and all states in $|xirangle$ are unmarked therefore,

$$O|chirangle =-|chirangle$$ $$O|xirangle =|xirangle$$

Thus by Linearity, $$O(sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle) = -sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle$$

Moreover it is important to note that $langlexi|chirangle =langlechi|xirangle=0$ as $|chirangle and |xirangle$ are orthogonal

Now, $$U = H^{otimes n}(2|0ranglelangle0|-I)H^{otimes n} = 2H^{otimes n}|0ranglelangle0|H^{otimes n} - I $$

We note that $H^{otimes n}|0rangle = frac{1}{N}sum_{x=0}^{N-1}|xrangle = |psirangle = sinfrac{theta}{2}|chirangle + cosfrac{theta}{2}|xirangle$

Thus, $$ U = 2|psiranglelangle psi| - I = 2(sinfrac{theta}{2}|chirangle + cosfrac{theta}{2}|xirangle)(sinfrac{theta}{2}langlechi| + cosfrac{theta}{2}langlexi|) - I = 2(sin^2frac{theta}{2}|chiranglelanglechi| + cosfrac{theta}{2}sinfrac{theta}{2}|xiranglelanglechi| + cosfrac{theta}{2}sinfrac{theta}{2}|chiranglelanglexi| + cos^2frac{theta}{2}|xiranglelanglexi|) - I$$

Therefore for $G^{k+1}|psirangle$ $$G^{k+1}|psirangle = GG^k|psirangle = G(sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle) = UO(sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle) = U(-sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle) = (2(sin^2frac{theta}{2}|chiranglelanglechi| + cosfrac{theta}{2}sinfrac{theta}{2}|xiranglelanglechi| + cosfrac{theta}{2}sinfrac{theta}{2}|chiranglelanglexi| + cos^2frac{theta}{2}|xiranglelanglexi|) - I) (-sinfrac{(2k+1)theta}{2}|chirangle + cosfrac{(2k+1)theta}{2}|xirangle) $$

If we expand this expression, cancel out the terms where inner product is zero and combine the coefficients involving the same state we get,

$$ G^R|psirangle = (-(2sin^2frac{theta}{2}-1)sinfrac{(2k+1)theta}{2} + (2cosfrac{theta}{2}sinfrac{theta}{2})cosfrac{(2k+1)theta}{2})|chirangle + (-(2cosfrac{theta}{2}sinfrac{theta}{2})sinfrac{(2k+1)theta}{2} + (2cos^2frac{theta}{2}-1)cosfrac{(2k+1)theta}{2})|xirangle$$

Using some trigonometry we can simply it further $$ G^R|psirangle = (costhetasinfrac{(2k+1)theta}{2} + sinthetacosfrac{(2k+1)theta}{2})|chirangle + (-sinthetasinfrac{(2k+1)theta}{2} + costhetacosfrac{(2k+1)theta}{2})|chirangle = sin(theta + frac{(2k+1)theta}{2})|chirangle + cos(theta + frac{(2k+1)theta}{2})|xirangle = sinfrac{(2k+3)theta}{2}|chirangle + cosfrac{(2k+3)theta}{2}|xirangle = sinfrac{(2(k+1)+1)theta}{2}|chirangle + cosfrac{(2(k+1)+1)theta}{2}|xirangle $$

This is exactly what we wanted. Hence our proof by Mathematical Induction is complete.

QED