J'ai essayé de résoudre TSP avec QAOA

Aperçu

Cet article présente l'implémentation lors de la résolution de TSP (Travelling Salesman Problem) avec QAOA (Quantum Approximate Optimization Algorithm), qui est l'un des algorithmes quantiques. Ici, la méthode utilisant Qiskit Aqua est adoptée sans effectuer de programmation quantique. Le langage est Python 3.7 et Qiskit fourni par IBM est utilisé. Veuillez ne pas demander de détails car il s'agit d'un mémorandum.

Qu'est-ce que QAOA?

Il est considéré comme l'un des algorithmes NISQ, et est un algorithme pour trouver la solution du problème d'optimisation de combinaison, similaire au recuit quantique. Une explication détaillée est évitée ici.

QISKIT Qiskit est un framework open source pour les ordinateurs quantiques. Dans cet article, Qiskit Aqua est utilisé. Il s'agit d'un outil que les utilisateurs peuvent utiliser sans effectuer eux-mêmes de programmation quantique. Actuellement, les domaines de la chimie, de l'IA, de l'optimisation et de la finance sont pris en charge.

TSP Le problème du voyageur de commerce est un problème d'optimisation de combinaison qui trouve celui avec le coût total de voyage le plus bas parmi les circuits itinérants qui font le tour de toutes les villes exactement une fois et reviennent au point de départ lorsqu'un ensemble de villes est donné.

Résolvez TSP avec QAOA

Importer la bibliothèque

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

Organisme du programme

python


#Nombre de villes
n = 3
#Obtenir les coordonnées(X dans la plage de 0 à 100,Obtenez les coordonnées y. Le troisième argument est la taille de la matrice)
coord = aqua_globals.random.uniform(0, 100, (n, 2))
#Convertissez en TSPData. Créer une matrice adjacente à partir des coordonnées données
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)

Voir les résultats

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))

Données TSP lorsque 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.]]))

résultat

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

Résumé

Un mémorandum sur l'utilisation de Qiskit Aqua. J'ai trouvé incroyable que QAOA puisse être utilisé sans aucune connaissance de la programmation quantique. Cependant, comme il se trouve sur le simulateur, le calcul prend beaucoup de temps. De plus, j'étais inquiet du résultat de [0,0,0]. Enfin, depuis que je l'ai posté sur Qiita pour la première fois, il peut être difficile à lire. Je suis désolé.

Post-scriptum: Actuellement, je travaille dur pour créer un circuit de cuillère à café

Recommended Posts

J'ai essayé de résoudre TSP avec QAOA
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python
J'ai essayé de résoudre le problème d'optimisation des combinaisons avec Qiskit
J'ai essayé d'implémenter Autoencoder avec TensorFlow
J'ai essayé de visualiser AutoEncoder avec TensorFlow
J'ai essayé de commencer avec Hy
J'ai essayé de laisser optuna résoudre le nombre
Je voulais résoudre ABC172 avec Python
J'ai essayé de déboguer.
J'ai essayé de prédire l'année prochaine avec l'IA
J'ai essayé d'implémenter la lecture de Dataset avec PyTorch
J'ai essayé d'utiliser lightGBM, xg boost avec Boruta
J'ai essayé d'apprendre le fonctionnement logique avec TF Learn
J'ai essayé de déplacer GAN (mnist) avec keras
Je voulais résoudre NOMURA Contest 2020 avec Python
J'ai essayé de sauvegarder les données avec discorde
J'ai essayé de détecter rapidement un mouvement avec OpenCV
J'ai essayé d'intégrer Keras dans TFv1.1
J'ai essayé de sortir LLVM IR avec Python
J'ai essayé de détecter un objet avec M2Det!
J'ai essayé d'automatiser la fabrication des sushis avec python
Je veux résoudre APG4b avec Python (chapitre 2)
J'ai essayé d'utiliser Linux avec Discord Bot
J'ai essayé d'étudier DP avec séquence de Fibonacci
J'ai essayé de démarrer Jupyter avec toutes les lumières d'Amazon
J'ai essayé de juger Tundele avec Naive Bays
Comment écrire en temps réel hors ligne J'ai essayé de résoudre E12 avec python
J'ai essayé d'entraîner la fonction péché avec chainer
J'ai essayé fp-growth avec python
J'ai essayé de gratter avec Python
J'ai essayé d'extraire des fonctionnalités avec SIFT d'OpenCV
J'ai essayé de déplacer Faster R-CNN rapidement avec pytorch
J'ai essayé d'apprendre PredNet
J'ai essayé de lire et d'enregistrer automatiquement avec VOICEROID2 2
J'ai essayé d'implémenter et d'apprendre DCGAN avec PyTorch
J'ai essayé Learning-to-Rank avec Elasticsearch!
J'ai essayé d'implémenter Mine Sweeper sur un terminal avec python
J'ai essayé de démarrer avec le script python de blender_Part 01
J'ai essayé de toucher un fichier CSV avec Python
J'ai essayé d'organiser SVM.
J'ai essayé le clustering avec PyCaret
J'ai essayé de lire et d'enregistrer automatiquement avec VOICEROID2
J'ai essayé de démarrer avec le script python de blender_Partie 02
J'ai essayé de générer ObjectId (clé primaire) avec pymongo
Je veux résoudre SUDOKU
J'ai essayé d'implémenter le perceptron artificiel avec python
J'ai essayé de créer un pipeline ML avec Cloud Composer
J'ai essayé de découvrir notre obscurité avec l'API Chatwork
J'ai essayé de réintroduire Linux
[Introduction à Pytorch] J'ai essayé de catégoriser Cifar10 avec VGG16 ♬
J'ai essayé de présenter Pylint
J'ai essayé de résumer SparseMatrix