Skip to main content
Quantum Computing

Return to Question

edited tags
Link
glS ♦
glS ♦
  • 26.9k
  • 6
  • 35
  • 121
small formatting issue
Source Link
edit approved Dec 3, 2020 at 13:35
luciano
edit approved Dec 3, 2020 at 13:35
luciano
  • 6k
  • 1
  • 13
  • 34

I have been trying to implement a QAOA for solving a traveling salesman problem (TSP) using $\texttt{qulacs}$qulacs and $\texttt{python}$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 $\texttt{scipy.optimize.minimize}$scipy.optimize.minimize function with the Nelder-Mead method. I realised that the resulting optimal angles are highly dependenddependent 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?

I have been trying to implement a QAOA for solving a traveling salesman problem (TSP) using $\texttt{qulacs}$ and $\texttt{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 $\texttt{scipy.optimize.minimize}$ function with the Nelder-Mead method. I realised that the resulting optimal angles are highly dependend 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?

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?

Source Link
ile2N
ile2N
  • 155
  • 5

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

I have been trying to implement a QAOA for solving a traveling salesman problem (TSP) using $\texttt{qulacs}$ and $\texttt{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 $\texttt{scipy.optimize.minimize}$ function with the Nelder-Mead method. I realised that the resulting optimal angles are highly dependend 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?