TSPをQAOAで解いてみた

#概要
本記事では，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の回路を作ろうと頑張っています