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


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


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.


| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.