[PYTHON] I tried to solve TSP with QAOA

Overview

This article introduces the implementation when solving TSP (Traveling Salesman Problem) with QAOA (Quantum Approximate Optimization Algorithm), which is one of the quantum algorithms. Here, the method using Qiskit Aqua is taken without performing quantum programming. The language is Python 3.7, and Qiskit provided by IBM is used. Please do not ask for details as it is a memorandum.

What is QAOA?

It is considered as one of the NISQ algorithms, and is an algorithm for finding solutions to combinatorial optimization problems, similar to quantum annealing. Detailed explanation is avoided here.

QISKIT Qiskit is an open source framework for quantum computers. In this article, we use Qiskit Aqua. This is a tool that users can use without doing quantum programming themselves. Currently, the fields of chemistry, AI, optimization, and finance are supported.

TSP The traveling salesman problem is a combination optimization problem that finds the one with the lowest total travel cost among the traveling circuits that go around all the cities exactly once and return to the starting point when a set of cities is given.

Solve TSP with QAOA

Import library

python

from qiskit.aqua.translators.ising import tsp
from qiskit.aqua.input import EnergyInput
from qiskit import BasicAer
from qiskit.aqua.algorithms import QAOA
from qiskit.aqua.components.optimizers import  POWELL
from qiskit.aqua import QuantumInstance
from qiskit.aqua import aqua_globals

Program body

python

#Number of cities
n = 3
#Get coordinates(X in the range of 0-100,Get the y coordinate. The third argument is the size of the matrix)
coord = aqua_globals.random.uniform(0, 100, (n, 2))
#Convert to TSPData. Create an adjacency matrix from the given coordinates
ins = tsp.calc_distance(coord, 'tmp')

qubitOp, offset = tsp.get_tsp_qubitops(ins, penalty=1e5)
algo_input = EnergyInput(qubitOp)

seed = 10240

optimizer = POWELL()
qaoa = QAOA(qubitOp, optimizer, 1)

backend = BasicAer.get_backend('statevector_simulator')
quantum_instance = QuantumInstance(backend, seed_transpiler=seed)

result = qaoa.run(quantum_instance)

View results

python

x = tsp.sample_most_likely(result['eigvecs'][0])

print('energy:', result['energy'])
print('time:', result['eval_time'])
print('tsp objective:', result['energy'] + offset)

print('solution:', tsp.get_tsp_solution(x))

TSPData when n = 3

TspData(name='tmp', dim=3, coord=array([[66.73333554, 32.83574073],
       [45.99618836, 47.41884594],
       [45.92600616, 25.75398833]]), w=array([[ 0., 25., 22.],
       [25.,  0., 22.],
       [22., 22.,  0.]]))

result

energy: -348052.5262025418
time: 57.140453577041626
tsp objective: 252050.97379745822
solution: [2, 0, 1]

Summary

A memorandum of how to use Qiskit Aqua. I thought it was amazing that QAOA could be used without any knowledge of quantum programming. However, since it is on a simulator, it takes a long time to calculate. Also, I was worried about the result of [0,0,0]. Finally, since I posted it on Qiita for the first time, it may be difficult to read. I'm sorry.

Postscript: Currently I am working hard to make a tsp circuit