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

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
    
  
    








	


	
	








	
	
		

		
Leave a Reply 
	

	



	
		

	



	


	




        

            


                
					en_USEnglish				

            

            


                
                    
          						  zh_CN简体中文					          
                en_USEnglish