Changing qubits coefficients to trigonometric functions in Grover Algorithm

Question

In this paper, in Appendix B.1 (Grover's Search Algorithm and Grover Operator G), it does a change of coefficients, such as what is done for the Bloch Sphere, but for a many qubits system using only two vectors.

Firstly, it separates the uniform superposition

$$|{\psi}\rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}{|x\rangle} $$

in two desired states (based on Oracle "responses")

$$ |\psi\rangle = \sqrt{\frac{M}{N}}|\chi\rangle + \sqrt{\frac{N-M}{N}}|\xi\rangle$$

with

$$ |\chi\rangle = \frac{1}{\sqrt{M}}\sum_{x,f(x)=1}{|x\rangle} \quad,\quad |\xi\rangle = \frac{1}{\sqrt{N-M}}\sum_{x,f(x)=0}{|x\rangle} $$

where $N=2^n$ (with n being the number of qubits) and $M$ is the number of Maximal Cliques, in this case the number of states which $f(x)=1$, the states which would be flipped by the Oracle.

Then it changes the coefficients of each summation to trigonometric ones as follows

$$ |\psi\rangle = \sin{\frac{\theta}{2}}|\chi\rangle + \cos{\frac{\theta}{2}}|\xi\rangle$$

I could easily see that this transformation is correct and preserves $\langle\psi|\psi\rangle=1$, but I got confused on how to deduce it for a many qubits system and how to achieve a similar structure after applying the Grover Operator G R times as stated by the paper in the following equation

$$ G^R|\psi\rangle = \sin{\frac{(2R+1)\theta}{2}}|\chi\rangle + \cos{\frac{(2R+1)\theta}{2}}|\xi\rangle$$

Answer 1

We know that the Initial state $|\psi\rangle$ can be represented as $\sin\frac{\theta}{2}|\chi\rangle + \cos\frac{\theta}{2}|\xi\rangle$.

We can prove the result $G^R|\psi\rangle = \sin\frac{(2R+1)\theta}{2}|\chi\rangle + \cos\frac{(2R+1)\theta}{2}|\xi\rangle$ by Induction

Base Case

When $R=0$, $G^R=G^0=I$ and $2R+1=2\times0+1=1$. Thus $G^0|\psi\rangle = \sin\frac{(2\times 0+1)\theta}{2}|\chi\rangle + \cos\frac{(2\times 0+1)\theta}{2}|\xi\rangle = \sin\frac{\theta}{2}|\chi\rangle + \cos\frac{\theta}{2}|\xi\rangle = |\psi\rangle$ is true. Base Case Proven

Inductive Step

Let us assume this is true for $\forall R \leq k$ i.e. $G^{k}|\psi\rangle = \sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle $

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|0\rangle\langle0|-I)H^{\otimes n})O$ where $O$ is the oracle.

We know that since all states in $|\chi\rangle$ are marked and all states in $|\xi\rangle$ are unmarked therefore,

$$O|\chi\rangle =-|\chi\rangle$$ $$O|\xi\rangle =|\xi\rangle$$

Thus by Linearity, $$O(\sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle) = -\sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle$$

Moreover it is important to note that $\langle\xi|\chi\rangle =\langle\chi|\xi\rangle=0$ as $|\chi\rangle and |\xi\rangle$ are orthogonal

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

We note that $H^{\otimes n}|0\rangle = \frac{1}{N}\sum_{x=0}^{N-1}|x\rangle = |\psi\rangle = \sin\frac{\theta}{2}|\chi\rangle + \cos\frac{\theta}{2}|\xi\rangle$

Thus, $$ U = 2|\psi\rangle\langle \psi| - I \\ = 2(\sin\frac{\theta}{2}|\chi\rangle + \cos\frac{\theta}{2}|\xi\rangle)(\sin\frac{\theta}{2}\langle\chi| + \cos\frac{\theta}{2}\langle\xi|) - I \\ = 2(\sin^2\frac{\theta}{2}|\chi\rangle\langle\chi| + \cos\frac{\theta}{2}\sin\frac{\theta}{2}|\xi\rangle\langle\chi| + \cos\frac{\theta}{2}\sin\frac{\theta}{2}|\chi\rangle\langle\xi| + \cos^2\frac{\theta}{2}|\xi\rangle\langle\xi|) - I$$

Therefore for $G^{k+1}|\psi\rangle$ $$G^{k+1}|\psi\rangle = GG^k|\psi\rangle = G(\sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle) \\ = UO(\sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle) \\ = U(-\sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle) \\ = (2(\sin^2\frac{\theta}{2}|\chi\rangle\langle\chi| + \cos\frac{\theta}{2}\sin\frac{\theta}{2}|\xi\rangle\langle\chi| + \cos\frac{\theta}{2}\sin\frac{\theta}{2}|\chi\rangle\langle\xi| + \cos^2\frac{\theta}{2}|\xi\rangle\langle\xi|) - I)\\ (-\sin\frac{(2k+1)\theta}{2}|\chi\rangle + \cos\frac{(2k+1)\theta}{2}|\xi\rangle)\\ $$

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|\psi\rangle \\ = (-(2sin^2\frac{\theta}{2}-1)\sin\frac{(2k+1)\theta}{2} + (2\cos\frac{\theta}{2}\sin\frac{\theta}{2})\cos\frac{(2k+1)\theta}{2})|\chi\rangle \\ + (-(2\cos\frac{\theta}{2}\sin\frac{\theta}{2})\sin\frac{(2k+1)\theta}{2} + (2cos^2\frac{\theta}{2}-1)\cos\frac{(2k+1)\theta}{2})|\xi\rangle$$

Using some trigonometry we can simply it further $$ G^R|\psi\rangle \\ = (\cos\theta\sin\frac{(2k+1)\theta}{2} + \sin\theta\cos\frac{(2k+1)\theta}{2})|\chi\rangle \\ + (-\sin\theta\sin\frac{(2k+1)\theta}{2} + \cos\theta\cos\frac{(2k+1)\theta}{2})|\chi\rangle \\ = \sin(\theta + \frac{(2k+1)\theta}{2})|\chi\rangle + \cos(\theta + \frac{(2k+1)\theta}{2})|\xi\rangle \\ = \sin\frac{(2k+3)\theta}{2}|\chi\rangle + \cos\frac{(2k+3)\theta}{2}|\xi\rangle \\ = \sin\frac{(2(k+1)+1)\theta}{2}|\chi\rangle + \cos\frac{(2(k+1)+1)\theta}{2}|\xi\rangle $$

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

QED