Optimization in QAOA should only return global minimum?

I am working on a project dealing with QAOA and I have some theoretical question about this last one. I hope I could find someone familiar with the field.

QAOA is usually used to solve combinatorial problems. The solution of the combinatorial problem will be encoded into the ground state energy on a problem tailored Hamiltonian, in this way we need our classical optimizer to be able to only find the global minimum -- i.e. the solution to the combinatorial problem. However, most of the time classical optimizers fail at finding the global minimum and will end up with local minima. In a scheme like machine learning, finding local minima usually does not matter but what about QAOA?

A priori, I have no guarantee that local minima in QAOA are good solutions to the combinatorial problem, right?

Is there anything in QAOA (like the landscape created by the circuit) that guarantees me that I should only find the GLOBAL minimum or that local minima are "good" approximate solutions?

Since QAOA is an approximation method I would assume it is impossible to find the global minimum each time but others seem to disagree...

• Commented Jun 11 at 21:03

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.

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.
• Thank you very much for your reply! Indeed, I remember that QAOA was derived from adiabatic computation and has the guarantee to be able to find the global optimum. I guess this part was not clear for me > With enough steps, QAOA is guaranteed to be able to find the optimal solution, since it generalizes the adiabitic 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). Since we use the same optimizer that are used in other scenar Commented Jun 11 at 13:22
• @baptistechev No problem! If my answer has been useful to you, don't hesitate to accept it. If you have further questions, please add them in comments here. I've converted your answer to a comment since the goal was to continue the discussion. But it seems that you've understood the reason why QAOA can't guarantee reaching the global optimum. As a side note though, the optimizers used in this case are generally not the same we use in ML, since we don't have access to a gradient information here. Commented Jun 11 at 13:28
• Sure I will do so! (I did not write as an answer since it could not make quotation ^^') And yeah I have been taking a bit a shortcut but I know for gradient-free methods even though gradient based methods can also be performed using parameter-shift rule if I am not mistaken. Commented Jun 11 at 13:37
• Very good answer and description of connection between adiabatic theorem and QAOA. +1 Commented Jun 11 at 21:01
• @Tristan "he adiabtic theorem essentially tells you that if you start in a ground state |ψ⟩ of Hp and make the system evolve slowly enough to Hs, then the state will always be a ground state of the current Hamiltonian." -- That's in fact not what the good (strong) versions of the adiabatic theorem say. All they say is that the final state will be close to the ground state. And if you numerically check what they do, you are in fact much further away from the ground state during the interpolation. (In essence, you are the closer to the ground state the more derivatives vanish, ... Commented Jun 13 at 20:10