4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.