前回記事はこちらから↓
はじめに
前回の記事では、クラウド（AWS）上で比較的手軽に動かせる量子インスパイアード・ハイブリッドソルバー QIH Solverの環境作成と、動作確認を行いました。
今回は自作したQUBOの問題をQIH Solverで解く方法について記載いたします。
以前qiitaに投稿した最大カット問題を例にpyquboで作成したquboをQIH Solverに投げることを前提にしています。
QUBO式の取り扱い
※ 本記事ではIsingについては取り扱いません。
QIH SolverのAMI環境に格納されたマニュアルには、QUBOで以下のように最適化をする旨が記載されております。
一般的な QUBO ですが、pyqubo/D-Wave 系の QUBO 辞書を“そのまま”は渡せないため、QIH Solverが受け付ける Q 行列に変換します。
pyqubo の to_qubo() は 係数辞書 Q と定数 offset を返します。
最大カットの例だと、以下のような辞書（抜粋）が得られます。
Q = {('H','H'):-46.45, ('D','D'):-47.17, ('H','A'):11.72, ...}
offset = ...
この辞書に格納された係数を用いてQ行列を作成することになります。
QUBO の 行列表現は以下のような形です。
- 扱うバイナリ変数の数 $N$ に対して $N \times N$ の行列を取る
-
対角は、係数をそのまま入れる（
Q[(i,i)] → Q_mat[i,i]） -
非対角は、係数を 1/2 にして対称に入れる（
Q[(i,j)] → Q_mat[i,j] += c/2, Q_mat[j,i] += c/2）
例えば、3 変数 (A, B, C) の問題で、to_qubo() が以下のような Q を返した場合、
Q = {("A", "A"): 2, ("A", "B"): 4, ("A", "C"): 8, ("B", "B"): 5, ("B", "C"): 6, {"C", "C"}: 1}
これに対して行列を作ると以下のような感じになるかと思います。
| A | B | C | |
|---|---|---|---|
| A | 2 | 2 | 4 |
| B | 2 | 5 | 3 |
| C | 4 | 3 | 1 |
[ [2, 2, 4]
[2, 5, 3]
[4, 3, 1] ]
上記のようなQ行列をQIH Solverに入力することで解を得ることができるようになります。
例題の最大カット問題ではハミルトニアンのモデルをto_qubo()したのちに、
以下のようなQ行列を作成するような処理を実行することでQIH Solverの処理に入れることができます。
import numpy as np
import pyqubo
def qubo_dict_to_matrix(Q_dict, var_order):
n = len(var_order) # ここが10なら 10×10
pos = {v:i for i,v in enumerate(var_order)}
Q = np.zeros((n, n), dtype=float)
for (vi, vj), c in Q_dict.items():
i, j = pos[vi], pos[vj]
if i == j:
Q[i, i] += c
else:
Q[i, j] += c/2.0
Q[j, i] += c/2.0
return Q
model = H.compile() # H: ハミルトニアンの式
Q, offset = model.to_qubo()
# 例：10ノード
var_order = ["A","B","C","D","E","F","G","H","I","J"]
Q_mat = qubo_dict_to_matrix(Q, var_order)
# Q_matをQIH Solverで実行
import TuringQHeuristic as TQ
TIMEOUT = 180
# QIH Solverの設定
SOLVER = TQ.QHeuristic(inputQuad=Q_mat,inputLinear=None,problemType='QUBO',timeout=TIMEOUT)
# 実行
SOLVER.main_solver()
おわりに
今回は自作した問題でのquboをQIH Solverを用いて解く方法についてを簡単にまとめました。
思っていたよりも簡単に自作問題についてもQIH Solverで取り扱うことができてよかったです。
またpyquboの辞書型の中身についてあまり理解していない部分もありましたが、今回調べたことで少し理解が進んだかと思います。
次回は、他の問題も扱いつつ、OpenJijとの比較などできればと思います。