How to do the direct evaluation by hand in QAOA algorithm

Question

In QAOA algorithm, for $p=1$ layer of gates and at most degree $d=3$, the expectation value can be calculated by hand. I think I can convince myself the idea of commutability. In this qiskit example, the author evaluated

$$f_A(\gamma,\beta) = \frac{1}{2}\left(1 - \langle +^3|U_{21}(\gamma)U_{02}(\gamma)U_{01}(\gamma)X_{0}(\beta)X_{1}(\beta)\;Z_0Z_1\; X^\dagger_{1}(\beta)X^\dagger_{0}(\beta)U^\dagger_{01}(\gamma)U^\dagger_{02}(\gamma)U^\dagger_{12}(\gamma) | +^3 \rangle \right)$$

as

$$f_A(\gamma,\beta) = \frac{1}{2}\left(sin(4\gamma)sin(4\beta) + sin^2(2\beta)sin^2(2\gamma)\right).$$

I believe I can write these unitaries explicitly as tensor product of $U1$ and $U3$ gate. However, when we evaluate this by hand, the states $|+^3\rangle$ or $|+^5\rangle$ what I can imagine is an 8-dimensional vector or 32-dimensional vector. For the 8-dimension case, these gates are two-qubit gates. All I can think of is that I need to expand these two-qubit gates into a three-qubit gate by tensor product with an identity operator. Even though, I still don't know how to handle these gates like $U_{02}$. How can I sandwich an identity operator into a two-qubit operator?

My question is how to evaluate this explicitly by hand.

I found a paper Quantum Algorithms for Fixed Qubit Architectures and it provided some operator identity which I think can help understand how this evaluation worked.

But I still have no idea how these identities hold.

I copied the original text here:

5.2 Optimal trial state parameters

In this example we consider the case for $p = 1$, i.e. only layer of gates. The expectation value $F_1(\gamma,\beta) = \langle \psi_1(\beta,\gamma)|H|\psi_1(\beta,\gamma) \rangle$ can be calculated analytically for this simple setting. Let us discuss the steps explicitly for the Hamiltonian $H = \sum_{(j,k) \in E} \frac{1}{2}\left(1 - Z_i Z_k\right)$. Due to the linearity of the expectation value we can compute the expectation value for the edges individually

$$f_{(i,k)}(\beta,\alpha) = \langle \psi_1(\gamma,\beta)|\;\frac{1}{2}\left(1 - Z_i Z_k\right)\;|\psi_1(\gamma,\beta)\rangle. $$ For the butterfly graph as plotted above, we observe that there are only two kinds of edges $A = \{(0,1),(3,4)\}$ and $B = \{(0,2),(1,2),(2,3),(2,4)\}$. The edges in $A$ only have two neighboring edges, while the edges in $B$ have four. You can convince yourself that we only need to compute the expectation of a single edge in each set since the other expectation values will be the same. This means that we can compute $F_1(\gamma,\beta) = 2 f_A(\gamma,\beta) + 4f_B(\gamma,\beta)$ by evaluating only computing two expectation values. Note, that following the argument as outlined in section 4.2.2, all the gates that do not intersect with the Pauli opertor $Z_0Z_1$ or $Z_0Z_2$ commute and cancel out so that we only need to compute

$$f_A(\gamma,\beta) = \frac{1}{2}\left(1 - \langle +^3|U_{21}(\gamma)U_{02}(\gamma)U_{01}(\gamma)X_{0}(\beta)X_{1}(\beta)\;Z_0Z_1\; X^\dagger_{1}(\beta)X^\dagger_{0}(\beta)U^\dagger_{01}(\gamma)U^\dagger_{02}(\gamma)U^\dagger_{12}(\gamma) | +^3 \rangle \right)$$ and

$$f_B(\gamma,\beta) = \frac{1}{2}\left(1 - \langle +^5|U_{21}(\gamma)U_{24}(\gamma)U_{23}(\gamma)U_{01}(\gamma)U_{02}(\gamma)X_{0}(\beta)X_{2}(\beta)\;Z_0Z_2\; X^\dagger_{0}(\beta)X^\dagger_{2}(\beta)U^\dagger_{02}(\gamma)U^\dagger_{01}(\gamma)U^\dagger_{12}(\gamma)U^\dagger_{23}(\gamma)U^\dagger_{24}(\gamma) | +^5 \rangle \right)$$ How complex these expectation values become in general depend only on the degree of the graph we are considering and is independent of the size of the full graph if the degree is bounded. A direct evaluation of this expression with $U_{k,l}(\gamma) = \exp\frac{i\gamma}{2}\left(1 - Z_kZ_l\right)$ and $X_k(\beta) = \exp(i\beta X_k)$ yields

$$f_A(\gamma,\beta) = \frac{1}{2}\left(sin(4\gamma)sin(4\beta) + sin^2(2\beta)sin^2(2\gamma)\right)$$ and

$$f_B(\gamma,\beta) = \frac{1}{2}\left(1 - sin^2(2\beta)sin^2(2\gamma)cos^2(4\gamma) - \frac{1}{4}sin(4\beta)sin(4\gamma)(1+cos^2(4\gamma))\right) $$ These results can now be combined as described above, and the expectation value is therefore given by

$$ F_1(\gamma,\beta) = 3 - \left(sin^2(2\beta)sin^2(2\gamma)- \frac{1}{2}sin(4\beta)sin(4\gamma)\right)\left(1 + cos^2(4\gamma)\right),$$ We plot the function $F_1(\gamma,\beta)$ and use a simple grid search to find the parameters $(\gamma^*,\beta^*)$ that maximize the expectation value.

Answer 1

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,

$$ e^{i{(X_i+X_j)}}=e^{i((X_i\otimes I_j)+(I_i \otimes X_j))}=e^{iX_i}e^{iX_j}. $$

Now, $$ \begin{align} 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{align} $$

Thus,

$$ \begin{align} e^{i \beta X} & = I\cos(\beta)+iX\sin(\beta). \end{align} $$

Hence,

$$ \begin{align} 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{align} $$

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

$$ \begin{align} 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{align} $$ We can calculate two-qubit operations independently, such that

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

Numerically, if you cannot convince yourself,

$$ Y_i \otimes I_k = \begin{bmatrix} &&-i&\\&&&-i\\i&&&\\&i&& \end{bmatrix} $$

and

$$ Z_i \otimes Z_k = \begin{bmatrix} 1&&&\\&-1&&\\&&-1&\\&&& 1\end{bmatrix} $$

and

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

Now, for a more specific example, $$ \begin{align} 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{align} $$

Q.E.D.