Since QAOA is an approximation method I would assume it is impossible to find the global minimum each time but others seem to disagree...
There's a difference between
- being guaranteed to find the global optimum;
- being guaranteed to be able to find the global optimum;
- being able to find the global optimum.
QAOA falls in the last two categories. If its number of steps is large enough, you're guaranteed that the optimal solution can be reached (but not that it will!). With a small number of steps, you may find the optimal solution, but you're not even sure that it can actually be reached. In all cases, because of how QAOA was designed, there is no guarantee that it will find the global optimum.
Background: the adiabatic theorem
Originally, there was the adiabatic theorem. In order to use it, we encode our problem into a Hamiltonian $H_p$ and we move it slowly enough to the Hamiltonian $H_s$ that encode our solution. The solution we're interested about is a ground state of this Hamiltonian.
Now, the adiabatic theorem essentially tells you that if you start in a ground state $|\psi\rangle$ of $H_p$ and make the system evolve slowly enough to $H_s$, then the final state will be close to a ground state of the final Hamiltonian $H_s$, which represents our desired solution.
So, in order to do it, we first choose a number of steps $N$ and during iteration number $i$ we apply some gates so that our Hamiltonian becomes:
$$\frac{N-i}{N}H_p+\frac{i}{N}H_c.$$
In order to do so approximately, we apply the operator $U\left(H_p, \frac{N-i}{N}\right)U\left(H_s, \frac{i}{N}\right)$, with:
$$U(H, t)=\mathrm{e}^{-\mathrm{i}tH}.$$
But in order for the adiabatic theorem to apply, the discretization must be fine, that is, $N$ must be very large, which isn't convenient, as it accumulates errors as time goes. But assuming everything goes well, you are guaranteed to find the optimal solution to your problem. And just to sum up, the operator that you end up applying is:
$$U\left(H_s, 1\right)U\left(H_p, \frac{1}{N}\right)U\left(H_s, \frac{N-1}{N}\right)\cdots U\left(H_p, \frac{N-1}{N}\right)U\left(H_s, \frac{1}{N}\right)$$
Moving back to QAOA
The idea behind QAOA is basically:
That chain of operators is quite long, let's take a shorter one. But since we restrict the algorithm, let us give it more freedom by allowing it to choose the angles in the unitaries.
And you have QAOA. You can easily see that be doing so, you no longer have a guarantee to find the global optimum, you just make a guess that a shorter sequence of unitaries with arbitrary angles can do the job. Fundamentally, you can see QAOA as a generalization of the adiabatic method described above: take the number of steps to be large enough and the optimization may be able to find back the angles describing the slow evolution. But that's not the point: our goal is to have a small number of steps, so that we can actually implement it.
Of course, this begs the question:
Why on earth would this work?
Followed by:
Why on earth does this work?!
To which I answer... I don't know (and if I'm not mistaken, that's also the case of most people). Intuitively, you just have an algorithm with quite a lot of freedom, since you allowed arbitrary angles in your unitaries. So surely, with enough freedom, you've got to get a good result at some point. And it's not like the cost function defined over the parameters (that are, the angles) is random: it's at least definitely continuous. Since we have some tools allowing us to find approximate solutions for such optimization problems, we just launch them at this black-box problem and they do their job.
And here you have QAOA. To sum up:
- QAOA is inspired by the adiabatic theorem, that allows to find the global optimum of the problem you're considering.
- With enough steps, QAOA is guaranteed to be able to find the optimal solution, since it generalizes the adiabatic theorem, but there is no guarantee that the classical optimization over the angles will find this optimum (in fact, with too much steps, you'll have too much parameters and thus won't probably find the global optimum).
- With a few number of steps, you still have some freedom so you can have some hope that you'll find a good enough solution.
