A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader

Headnotes

Many equations and formulas look intimidating. However, when you hunt them down, they are definitely not! Just papertigers!
Now let's hunt the papertiger.

This is not finished.
2020-07-30 first commit

The problem definition

QAOA​1​

Traverse field Ising model

Adibatic quantum computation

Circuit design

Coding

Trival state preparation

After several days of thinking and researching, I decided to answer my own question.

N.B. The tensor product symbol \otimes are omitted when there is no risk in confusion, especially when the index is different. In symbol,A_iB_j = A_i \otimes B_j (i \neq j).

Firstly, for case e^{i \beta B} Z_i Z_j e^{-i \beta B}, we only consider qubit j, in which B_e=\sum_{k \in e}{X_k}. As X_i and X_j act on different qubits,

 (1)    \begin{equation*}e^{i{(X_i+X_j)}}=e^{i((X_i\otimes I_j)+(I_i \otimes X_j))}=e^{iX_i}e^{iX_j}.\end{equation*}

Now,

 (2)    \begin{equation*} \begin{aligned} e^{-i \beta X} & = e^{-i \beta \begin{bmatrix}0 & 1\\ 1 & 0\end{bmatrix}} \\ & = e^{-i \beta \begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\end{bmatrix} \begin{bmatrix}1 & 0\\ 0 & 1\end{bmatrix} \begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\end{bmatrix}} \\ & = \begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\end{bmatrix} \begin{bmatrix}e^{-i \beta} & 0\\ 0 & e^{-i \beta}\end{bmatrix} \begin{bmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\end{bmatrix} \\ & = \begin{bmatrix}\cos(\beta) & -i\sin(\beta)\\ -i\sin(\beta) & \cos(\beta)\end{bmatrix} \\ & = I\cos(\beta)-iX\sin(\beta). \end{aligned} \end{equation*}

Thus,

 (3)    \begin{equation*}\begin{aligned}e^{i \beta X}& = I\cos(\beta)+iX\sin(\beta).\end{aligned}\end{equation*}

Hence,

 (4)    \begin{equation*}\begin{aligned}e^{i \beta X} Z e^{-i \beta X} & = (I\cos(\beta)+iX\sin(\beta))Z(I\cos(\beta)-iX\sin(\beta)) \\& = Z \cos(2\beta) + Y\sin(2\beta).\end{aligned}\end{equation*}

For the Ising traverse field Hamiltonian, we only consider G_{e=(i,k)}=Z_iZ_k.

For e^{i \gamma Z_iZ_k}, it can be evaluated as

 (5)    \begin{equation*} \begin{aligned} e^{i \gamma Z_iZ_k} = & e^{i \gamma \begin{bmatrix}1&&&\\&-1&&\\&&-1&\\&&&1\end{bmatrix}}  = \begin{bmatrix}e^{i\gamma}&&&\\&e^{-i\gamma}&&\\&&e^{-i\gamma}&\\&&&e^{i\gamma}\end{bmatrix} \\ = & \begin{bmatrix}\cos\gamma+i\sin\gamma &&&\\&\cos\gamma-i\sin\gamma&&\\&&\cos\gamma-i\sin\gamma&\\&&&\cos\gamma+i\sin\gamma\end{bmatrix} \\ = & \cos\gamma\begin{bmatrix}1&&&\\&1&&\\&&1&\\&&&1\end{bmatrix}+i\sin\gamma\begin{bmatrix}1&&&\\&-1&&\\&&-1&\\&&&1\end{bmatrix} \\ = & I_i I_k \cos\gamma + i Z_1Z_2 \sin\gamma. \end{aligned} \end{equation*}

We can calculate two-qubit operations independently, such that

 (6)    \begin{equation*}Y_i (Z_i Z_k) = (Y_i \otimes I_k)(Z_i \otimes Z_k)=(Y_i Z_i) \otimes (I_kZ_k) = i X_i \otimes Z_k = i X_i Z_k.\end{equation*}

Numerically, if you cannot convince yourself,

 (7)    \begin{equation*}Y_i \otimes I_k = \begin{bmatrix} &&-i&\\&&&-i\\i&&&\\&i&& \end{bmatrix}\end{equation*}

and

 (8)    \begin{equation*}Z_i \otimes Z_k = \begin{bmatrix} 1&&&\\&-1&&\\&&-1&\\&&& 1\end{bmatrix}\end{equation*}

and

 (9)    \begin{equation*}(Y_i \otimes I_k)(Z_i \otimes Z_k) = \begin{bmatrix} &&i&\\&&&-i\\i&&&\\&-i&&\end{bmatrix} = i(X_i \otimes Z_k).\end{equation*}

Now, for a more specific example,

 (10)    \begin{equation*} \begin{aligned} e^{-i \gamma Z_iZ_k} Y_i e^{i \gamma Z_iZ_k} & = (I_i I_k \cos\gamma - i Z_1Z_2 \sin\gamma) (Y_i \otimes I_k) (I_i I_k \cos\gamma + i Z_1Z_2 \sin\gamma) \\ & = Y_i \cos^2\gamma - Y_i\sin^2\gamma - X_i Z_k\sin\gamma\cos\gamma - X_i Z_k \sin\gamma\cos\gamma \\ & = Y_i \cos 2\gamma - X_iZ_k\sin 2\gamma. \end{aligned} \end{equation*}

Q.E.D.






Reference
  1.   
    
    
    1. 
    Choi J, Kim J. A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications. In: 2019 International Conference on Information and Communication Technology Convergence (ICTC). IEEE; 2019. doi:10.1109/ictc46691.2019.8939749
    
  
    










Footnotes

There are many excellent tutorials out there. Some tutorials are too intuitive and it's helpful, but you cannot get it straight on the math details. Some focused on dymestifying math. Some focused on code. I found the best tutorials that give you the conceptual ideas and are possible for implementation without being blind to the math details. Drop a comment if I failed. It would be really appreciable. 




If you want to cite this article, please cite this article as: 




Lachlan Chen, "A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader," in EarnFromScratch, July 30, 2020, https://www.earnfs.com/en/html/2021.htm.




or




@misc{lachlanchen2020tutorial,

title=A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader,

author={Chen, Lachlan},

year=July 30, 2020

}




EarnFromScratch (December 5, 2020) A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader. Retrieved from https://www.earnfs.com/en/html/2021.htm.
"A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader." EarnFromScratch - December 5, 2020, https://www.earnfs.com/en/html/2021.htm
EarnFromScratch July 30, 2020 A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader., viewed December 5, 2020,<https://www.earnfs.com/en/html/2021.htm>
EarnFromScratch - A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader. [Internet]. [Accessed December 5, 2020]. Available from: https://www.earnfs.com/en/html/2021.htm
"A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader." EarnFromScratch - Accessed December 5, 2020. https://www.earnfs.com/en/html/2021.htm
"A full tutorial on QAOA algorithm without leave-it-as-an-exercise-for-reader." EarnFromScratch [Online]. Available: https://www.earnfs.com/en/html/2021.htm. [Accessed: December 5, 2020]
 














	


	
	








	
	
		

		
Leave a Reply