🥅
量子アニーリングを用いたMIS問題へのアプローチ
筆者について
- 量子アニーリング初学者
- ネットワークを用いたポートフォリオ最適化に興味があり学習を開始（2025年4月）
- 備忘録的な感じ
はじめに
MIS問題（Minimum Independent Set problem: 最大独立集合問題）を量子アニーリングを用いて解いてみた
自分の学び・読者の変化
- 自分の学び
- toy exampleを通してQUBO行列の作成方法がイメージできた
- 読者の変化
- ネットワークの具体例を用いてMIS問題をイメージできる
開発環境
- Windows
- Vscode
- Jupyter Notebook
キーワード
-
MIS問題
- Minimum Independent Sets problem
- 最大独立集合問題
- 量子アニーリング
- NetworkX
- blueqat
事前準備
0.1. 仮想環境の作成
conda create -n quantum_annealing
0.2. ライブラリのインストール
- 必要に応じてnetworkx, numpy, matplotlibに関してもインストールする
- 自分の場合はblueqatのインストールだけで動いた
conda activate quantum_annealing
pip install blueqat==0.3.18
0.3. ライブラリのインポート
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import blueqat
import blueqat.wq as wq
print(blueqat.__version__)
import networkx as nx
print(nx.__version__)
やったこと
1. toy exampleの作成
- toy exampleを作成する
- 下のようなネットワークが作成できるはず
# 隣接行列
A = np.array([
[0,1,0,1,0,1],
[1,0,1,1,0,1],
[0,1,0,0,0,0],
[1,1,0,0,0,1],
[0,0,0,0,0,1],
[1,1,0,1,1,0]
])
# グラフ作成
G = nx.Graph(A)
# 描画
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, font_size=12)
plt.show()
2. 隣接行列の上三角化・単位行列の作成
- 隣接行列を右上三角行列に変換し、同じ大きさの単位行列を作成する
# 隣接行列を右上三角行列に変換する（制約項）
A_upper = np.triu(A)
print(A_upper)
# 6x6 の単位行列を生成する（目的項）
I = np.eye(6)
print(I)
3. 演算の実行
- blueqatを用いてシミュレーテッド・アニーリングを実行する
- QUBO行列やblueqatについては参考資料を参照のこと
- 係数（k, l）は仮に（2, 1）としている
- （1, 1）では安定しなかった
k, l = 2, 1
# wildqatのOptクラス
a = wq.Opt()
# QUBO行列の定義
a.qubo = (k*A_upper - l*I).tolist()
print(f"k: {k}, l: {l}")
for i in range(10):
print(f"x = {a.sa()}")
print(f"H = {a.E[-1]}")
# 出力例
k: 2, l: 1
x = [0, 0, 1, 1, 1, 0]
H = -3.0
x = [1, 0, 1, 0, 1, 0]
H = -3.0
x = [1, 0, 1, 0, 1, 0]
H = -3.0
x = [0, 0, 1, 1, 1, 0]
H = -3.0
x = [0, 0, 1, 1, 1, 0]
H = -3.0
x = [1, 0, 1, 0, 1, 0]
H = -3.0
x = [1, 0, 1, 0, 1, 0]
H = -3.0
x = [1, 0, 1, 0, 1, 0]
H = -3.0
x = [0, 0, 1, 1, 1, 0]
H = -3.0
x = [0, 0, 1, 1, 1, 0]
H = -3.0
まとめ
- 予想通りの結果が得られた
Discussion