Why do we add the cost function as a phase in QAOA?

Question

For QAOA, my understanding is that after we derive our cost Hamiltonian: $H_c|x$>$=C(x)x$ where $C(x)$ is the cost function on input x. We exponentiate it: $e^{-iH_c\theta}$, so we can simulate this Hamiltonian.

While doing so, we have effectively moved the value of the cost function as a phase.

Example

If $C(x)$ is defined as $C(0)=0$, $C(1)=1$ then:

$H=0.5(I-Z)=\begin{bmatrix} 0 & 0\\ 0 & 1 \end{bmatrix}$

We would then get $U_c=e^{-iH_c\theta}=\begin{bmatrix} e^{-i(0)\theta} & 0\\ 0 & e^{-i\theta} \end{bmatrix}$

Now we can see that $U_c|0$>$=e^{-i(0)\theta}|0$> and $U_c|1$>$=e^{-i\theta}|1$>

It looks like all we were trying to do was to add the cost function as a phase for our input. (And also varying that phase by some coefficient $\theta$)

Question

Why are we trying to do this? How does this help us in minimizing the hamiltonian (the cost function)?

Answer 1

It's not really the phase of the unitary that matters. The hamiltonian is the more important part.

However, the phase that the hamiltonian applys technically isn't useful in of itself, in the sense that it's the connection to Adiabatic Quantum Computing that allows us to choose an ansatz for VQE (which QAOA is just a special case of), which allows for some guarantees such as monotonically increasing accuracy from our classical optimizer as $p$, the number of iterations of the alternating unitaries, increases.