3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

TSPをQAOAで解いてみた

Last updated at Posted at 2019-12-29

#概要
本記事では,TSP(Traveling Salesman Problem)を量子アルゴリズムの一つであるQAOA(Quantum Approximate Optimization Algorithm)で解くときの実装を紹介しています.
ここでは量子プログラミングを行うことなくQiskit Aquaを用いる方法を取っています.
言語はPython3.7,IBMが提供するQiskitを使用しています.
備忘録なので詳しい内容は聞かないでください.

##QAOAとは
NISQアルゴリズムの一つとして考えられていて,量子アニーリングと同様に,組み合わせ最適化問題の解を求めるためのアルゴリズムである.
詳しい解説はここでは避ける.

##QISKIT
Qiskitとは量子コンピュータ用のオープンソースのフレームワークである.また,本記事ではQiskit Aquaを使う.これは,ユーザー自身が量子プログラミングを行うことなく使用できるツールである.現在,化学,AI,最適化,金融の分野がサポートされている.

##TSP
巡回セールスマン問題は,都市の集合が与えられたとき,すべての都市を丁度一度ずつ巡り出発地に戻る巡回路のうち,総移動コストが最小のものを求める組み合わせ最適化問題である.

#TSPをQAOAで解く
ライブラリをimportする

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

プログラム本体

#cityの数
n = 3
# 座標を取得(0~100の範囲でx,y座標を取得.三つ目の引数は行列のサイズ)
coord = aqua_globals.random.uniform(0, 100, (n, 2))
# TSPDataに変換.与えられた座標から隣接行列を作成
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)

結果を表示

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

n=3の時のTSPData

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

結果

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

#まとめ
Qiskit Aquaの使い方の備忘録です.
量子プログラミングの知識がなくてもQAOAが使えるというのはなかなか凄いことだと思いました.
しかし,シミュレーター上なので計算時間がかかることころが難点かなと.
また,[0,0,0]という結果が出るところが気になりましたね.
最後に,初めてQiitaで投稿したので読みにくいところがあるかもしれません.申し訳ありません.

追記:現在tspの回路を作ろうと頑張っています

3
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?