2019.05.17

【量子コンピューター】QAOAでMaxcutを解こう! (最終回)

須郷 聖也
こんにちは、テラスカイの須郷です。
今回は前回の続きで、QAOAというアルゴリズムについて簡単にご紹介したいと思います。
この記事の内容は先日行った以下の勉強会で私が発表した内容をブログ用に再度まとめ直したものとなります。

第2回 量子ゲートの最新状況を学ぶ - connpass

第2回 量子ゲートの最新状況を学ぶ - connpass
2019年2月13日に弊社テラスカイで行った量子コンピューター勉強会の第2回目です。この回では量子ゲートモデルの最新状況ということで、NISQに関連した3つの講演を社外の方も招いて分担して発表を行いました。

qiskitを用いたデモ

qiskit-aqua

qiskitにはqiskit-aquaというNISQ用のライブラリーがあります。今回はこちらを用いてデモを行っていきます。
qiskit-aquaにはQAOAで利用できる便利なツールがいくつか用意されています。
例えば、前回の記事で説明した古典量子の繰り返し計算で用いる古典用のオプティマイザーが複数用意されています(qiskit_aqua.components.optimizer内)。
さらに、Maxcut問題をはじめとしたいくつかのイジング型の問題をゲートモデルで扱うためのクラスも用意されています(qiskit_aqua.translators.ising内)。
以下ではこれらのツールやクラスを利用していきます。

2つの問題を解く

qiskit-aquaを用いて下図の2つの問題を解いていこうと思います。

Q1を解く

下のコードを実行してQ1を解いてみます。コードはqiskit-aqua内のコードを参考にしました。
まず、問題設定となる隣接行列を用意し、前の記事で紹介した時間の分割数pは1とします。
次に量子計算を行うバックエンドと古典計算を行うオプティマイザーを用意し、隣接行列からゲート演算子を用意します。これらを用いてQAOAの計算を実行します。
import numpy as np
from qiskit_aqua.algorithms import QAOA
from qiskit_aqua import get_aer_backend
from qiskit_aqua.translators.ising import maxcut
from qiskit_aqua.components.optimizers import COBYLA
from qiskit_aqua import QuantumInstance

# Q1
w = np.array([
    [0, 1, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 0]
])

p = 1
backend = get_aer_backend('statevector_simulator')
optimizer = COBYLA()
qubitOp, offset = maxcut.get_maxcut_qubitops(w)
qaoa = QAOA(qubitOp, optimizer, p, operator_mode='matrix')
quantum_instance = QuantumInstance(backend)
result = qaoa.run(quantum_instance)
x = maxcut.sample_most_likely(result['eigvecs'][0])
graph_solution = maxcut.get_graph_solution(x)
print('energy:             {}'.format(result['energy']))
print('time:               {}'.format(result['eval_time']))
print('maxcut objective:   {}'.format(result['energy'] + offset))
print('solution:           {}'.format(graph_solution))
print('solution objective: {}'.format(maxcut.maxcut_value(x, w)))
qaoa.py
上記コードの後半で、得られた結果を加工して出力しています。
solutionが今回得られたグループ分けの結果です。定式化の時には1, -1で説明をしていたものが今回は0,1となっています。この[0, 1, 0, 1]は左から順に頂点A, B, C, Dがどちらのグループに属しているかを表しており、AとC、BとDがそれぞれ同じグループに属している正しい解が得られていることがわかります。solution objectiveの値はカットした際の重みの合計を表しており、これも上で示した図で示した解とあっています。

同様にQ2を解いてみるが・・・？

同様にしてQ2も解いてみます。以下の通り、グラフの隣接行列をQ2のものに差し替えるだけです(変化させている部分のコードだけ抜粋して記載しています)。上の図を見ると最適な解はAとC、BとDが同じグループで、重みの合計は9となるはずですが・・・
# Q1
"""
w = np.array([
    [0, 1, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [1, 0, 1, 0]
])
"""

# Q2
w = np.array([
    [0, 2, 5, 1],
    [2, 0, 1, 0],
    [5, 1, 0, 2],
    [1, 0, 2, 0]
])
qaoa.py
結果をみてみるとAとB、CとDが同じグループとなっており、最適な解になっていません。
何度か計算を試してみましたが、いずれも同様の解が得られました。

オプティマイザーを変えてみる

Q2ではQ1と同じ方法で最適解がでないので、別の古典オプティマイザーを試してみました。
先ほどは参考にしたコードにならってCOBYLAと呼ばれるオプティマイザーを使用していましたが、今回はPOWELLと呼ばれるオプティマイザーを使用してみます。
#from qiskit_aqua.components.optimizers import COBYLA
from qiskit_aqua.components.optimizers import POWELL

#optimizer = COBYLA()
optimizer = POWELL()
qaoa.py
結果は以下の通りです。最適解が得られています。この結果から、古典オプティマイザーによって得られる解に差がでることがわかります。
今回私はそれぞれのオプティマイザーの違いまで踏み込んで理解しているわけではありませんが、QAOAに限らずNISQ用のアルゴリズムでは古典量子の繰り返し計算を行うものがみられるため、今後は古典オプティマイザーの違いを理解して使い分ける必要があると感じました。

最後に

ここまで3回に渡ってQAOAとMaxcut問題を取り扱ってきました。
組合せ最適化問題に関してはアニーリングと共通する知識が多く、特に定式化の部分(今回で言うとget_maxcut_qubitops関数)ができてしまえば、後のQAOA部分はツール側で担保してもらえそうです。
量子アルゴリズムの中身を深くまで理解するのは困難ですが、各社便利なツールを作成しているので、それらを有効活用したいですね。
また、古典量子の繰り返し計算を行うアルゴリズムに対しては古典側の計算に対する理解も必要であることを実感しました。
まだまだ簡単な問題しか扱っていませんが、みなさんの参考になれば幸いです。
26 件

関連する記事

関連するキーワード