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

Recommended Posts

I tried to solve TSP with QAOA
I tried to solve the soma cube with python
I tried to solve the problem with Python Vol.1
I tried to solve AOJ's number theory with Python
I tried to solve a combination optimization problem with Qiskit
I tried to implement Autoencoder with TensorFlow
I tried to visualize AutoEncoder with TensorFlow
I tried to get started with Hy
I tried to let optuna solve Sudoku
AtCoder Green tried to solve with Go
I wanted to solve ABC172 with Python
I tried to debug.
I tried to paste
I tried to predict next year with AI
I tried to detect Mario with pytorch + yolov3
I tried to implement reading Dataset with PyTorch
I tried to use lightGBM, xgboost with Boruta
I tried to learn logical operations with TF Learn
I tried to move GAN (mnist) with keras
I wanted to solve NOMURA Contest 2020 with Python
I tried to save the data with discord
I tried to detect motion quickly with OpenCV
I tried to integrate with Keras in TFv1.1
I tried to output LLVM IR with Python
I tried to detect an object with M2Det!
I tried to automate sushi making with python
I want to solve APG4b with Python (Chapter 2)
I tried to operate Linux with Discord Bot
I tried to study DP with Fibonacci sequence
I tried to start Jupyter with Amazon lightsail
I tried to judge Tsundere with Naive Bayes
How to write offline real time I tried to solve E12 with python
I tried to learn the sin function with chainer
I tried fp-growth with python
I tried scraping with Python
I tried to create a table only with Django
I tried to extract features with SIFT of OpenCV
I tried to move Faster R-CNN quickly with pytorch
I tried to learn PredNet
I tried to read and save automatically with VOICEROID2 2
I tried to implement and learn DCGAN with PyTorch
I tried Learning-to-Rank with Elasticsearch!
I tried to implement Minesweeper on terminal with python
I tried to get started with blender python script_Part 01
I tried to touch the CSV file with Python
I tried to organize SVM.
I tried clustering with PyCaret
I tried to automatically read and save with VOICEROID2
I tried to get started with blender python script_Part 02
I tried to generate ObjectId (primary key) with pymongo
I want to solve Sudoku (Sudoku)
I tried to implement an artificial perceptron with python
I tried to build ML Pipeline with Cloud Composer
I tried to implement time series prediction with GBDT
I tried to uncover our darkness with Chatwork API
I tried to automatically generate a password with Python3
I tried to reintroduce Linux
[Introduction to Pytorch] I tried categorizing Cifar10 with VGG16 ♬
I tried to introduce Pylint
I tried to summarize SparseMatrix
I tried to analyze J League data with Python