# Changing qubits coefficients to trigonometric functions in Grover Algorithm

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

• Something won't work with \ket and \braket in MathJax. Feb 24 '20 at 19:04
• Yeah, it was working while writing, but not after published... Weird. Now it's fixed Feb 24 '20 at 19:06
• Does this answer your question? How can Grover's operator be represented as a rotation matrix?
– glS
Aug 3 '20 at 5:56

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