Question about QAOA for MaxCut, and adiabatic evoution

Question

I'm experimenting with QAOA for solving some MaxCut instance, and I think I see conflicting explanations online and in the literature. Incidentally, I fail to reproduce the nice decreasing cost/iteration curve of https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm ...

First, let me fix some notations.

1. The graph interest is $G = (V, E)$, it has $N$ vertices, and for simplicity, is unweighted;
2. the mixer is $H_M = \sum_j X_j$;
3. the cost operator is $H_C = \sum_{(j, k) \in E} Z_j Z_k$;
4. the initial state is $\left| s \right\rangle = H^{\otimes N} \left| 0 \right\rangle = \sum_{j = 0}^{2^N-1} \left| j \right\rangle$.

Already there are some conflicts, as other sources define the mixer and cost as

5. sometimes $H_M^- = - H_M = - \sum_j X_j$;
6. and some other times $H_C^- = - H_C = - \sum_{(j, k) \in E} Z_j Z_k$ (module some weights).

But let's carry on. The QAOA ansatz / evolution operator reads $$ U (\beta, \gamma) = e^{- i \gamma_k H_M} e^{- i \beta_k H_C} \cdots e^{- i \gamma_1 H_M} e^{- i \beta_1 H_C} $$ where $\beta_1, \ldots, \beta_k, \gamma_1, \ldots, \gamma_k$ are variational parameters to be optimized classically by minimizing the cost function $$ E(\beta, \gamma) = \left\langle s | U (\beta, \gamma)^\dagger H_C U (\beta, \gamma) | s \right\rangle . $$

For good measure, and in case it make it easier to write an response, let's write

7. $U (\beta, \gamma)^{-+}$ for $U (\beta, \gamma)$ that uses $H_M^- = - H_M$ instead of $H_M$, likewise for $E (\beta, \gamma)^{-+}$;
8. $U (\beta, \gamma)^{+-}$ for using $H_C^- = - H_C$ instead of $H_C$, likewise for $E (\beta, \gamma)^{+-}$;
9. $U (\beta, \gamma)^{--}$ for using $H_M^-$ and $H_C^-$, and likewise for $E (\beta, \gamma)^{--}$.

OK SO. Adiabatic evolution says, in a few words, that starting with an initial ground state of an initial Hamiltonian and slowly transforming the initial Hamiltonian to a target Hamiltonian will result in a ground state of the target Hamiltonian. This is promising since a ground state of $H_C$ encodes a maximal cut of $G$. This is the approach described in e.g. https://learning.quantum.ibm.com/tutorial/quantum-approximate-optimization-algorithm .

HOWEVER, isn't our initial state $\left| s \right\rangle$ a highest energy state of our initial Hamiltonian $H_M$?

So instead, might we want to

10. set the mixer to $H_M^-$ and minimize $E (\beta, \gamma)^{-+}$?
11. set the cost operator to $H_C^-$ and maximize $E (\beta, \gamma)^{+-}$? this seems to be the approach of the original QAOA paper https://arxiv.org/pdf/1411.4028 as well as https://arxiv.org/pdf/2306.09198 section 2.5, https://arxiv.org/pdf/1804.03719 section 12.2, etc.

I have been banging my head against my desk for the past two days trying to reconcile all the sources I surveyed and obtain a working implementation. Any held would be g r e a t l y appreciated.

edit: corrected typo $\left\langle s | U (\beta, \gamma)^\dagger H_C U (\beta, \gamma) | s \right\rangle$ instead of $\left\langle s | U (\beta, \gamma) | s \right\rangle$.

Answer 1

There is a detail that you may have missed in the original paper (eqs 7, 8) is that you are not trying to optimise is not: $ E(\beta, \gamma) = \left\langle s | U (\beta, \gamma) | s \right\rangle . $

The value you want to optimise is the cost defined by the operator $H_C = \sum_{(j, k) \in E} Z_j Z_k$ for a state resulting from the circuit. Usually you are interested in either the optimum of the cost itself or the states that produce this result. This means that instead of looking at $E(\beta, \gamma)$ as you defined it, you would need to look at: $$C(\beta, \gamma) = \langle s|U(\beta,\gamma)^{\dagger}H_CU(\beta,\gamma)|s\rangle,$$ where $U(\beta,\gamma) = e^{- i \gamma_k H_M} e^{- i \beta_k H_C} \cdots e^{- i \gamma_1 H_M} e^{- i \beta_1 H_C}$.

This is where Matti's comment comes into play. Minimising the cost function is equivalent to maximising minus the cost function.

Answer 2

HOWEVER, isn't our initial state |s⟩ a highest energy state of our initial Hamiltonian HM?

No. In initial state spins point into random directions. If you can maximize optimization problem you can minimize it as well by changing a sign.