Classical optimisation of angles in QAOA for TSP gets stuck in local minima?

Question

I have been trying to implement a QAOA for solving a traveling salesman problem (TSP) using qulacs and python. However, even for 3 cities, the implementation fails. Within QAOA, we try to minimise $$ \begin{equation} F_p(\gamma,\beta) = \langle \gamma,\beta | C | \gamma,\beta\rangle, \end{equation} $$ where $C$ is the cost function of the TSP, and $|\gamma,\beta\rangle$ is a quantum state depending on these two angles. I had a closer look at my classical optimisation of the angles $\beta, \gamma$, for which I used the scipy.optimize.minimize function with the Nelder-Mead method. I realised that the resulting optimal angles are highly dependent on the initial angles. Additionally, I had a look at my cost function $C$. It seems like the optimisation got stuck in many local minima.

I have seen several implementations of a QAOA TSP using other software frameworks, and most of them also used scipy.optimize.minimize for the angles optimisation. Is getting stuck in local minima a known issue for QAOA TSP, or do I have to search for another error source? If the first, how can I overcome this issue?

Answer 1

Yes it is. It's not only on TSP but in most (if not all) NP-hard combinatorial problems.

The landscape of the loss-function is highly non-convex and is filled with local minima. That is, starting an optimization from different initial points will lead in different minima. A way to address this problem is with multi-start methods (i.e. start from many different initial points). An interesting paper I've found is this:

https://arxiv.org/abs/1905.08768

Another way for addressing the point is with Reinforcement Learning methods, because even if you stuck in a local minimum, with some small probability you will still explore in the parameter landscape and thus find a better local or a global minimum.