はじめに
前回、MAX-CUT問題をQUBO形式へ落とし込むところまで進めた。
今回はGPUに対応したプログラムを実装し、CPU実装と性能を比較した結果と考察をまとめる。
※本記事にはAIで生成した動作検証済みのコードが含まれます
実装
環境構築
まず必要なパッケージをインストールする。
# requirements.txt
tytan>=1.2.0
networkx>=3.0
matplotlib>=3.5.0
numpy>=1.21.0
pandas>=1.3.0
tqdm>=4.62.0
torch>=2.0.0 # CUDA対応版
QUBO行列の生成
MAX-CUT問題をQUBO形式に変換する実装
$xi ≠ xj$ のときにのみエネルギーが -1 となるため、エネルギー最小化がカット数最大化に対応する。
def create_maxcut_qubo(graph: nx.Graph) -> Tuple[Dict[Tuple[str, str], float], float]:
"""
MAX-CUT問題のQUBO行列を生成
エネルギー関数: E = Σ(-xi - xj + 2*xi*xj) を最小化
"""
qubo = {}
for i, j in graph.edges():
var_i = f'x{i}'
var_j = f'x{j}'
# 線形項: -xi と -xj
if (var_i, var_i) not in qubo:
qubo[(var_i, var_i)] = 0
if (var_j, var_j) not in qubo:
qubo[(var_j, var_j)] = 0
qubo[(var_i, var_i)] += -1
qubo[(var_j, var_j)] += -1
# 二次項: +2*xi*xj
if i <= j:
key = (var_i, var_j)
else:
key = (var_j, var_i)
if key not in qubo:
qubo[key] = 0
qubo[key] += 2
return qubo, 0
GPU/CPU疑似量子アニーリングソルバー
Tytan SDKを使ったGPU/CPU実装
class TytanSolver:
def __init__(self, use_gpu: bool = True, seed: Optional[int] = None):
self.use_gpu = use_gpu
self.seed = seed
def solve_maxcut(self, graph: nx.Graph, num_reads: int = 1000):
# QUBOへ変換
qubo_dict, offset = create_maxcut_qubo(graph)
# Tytanのシンボル変数を作成
variables = {}
for i in graph.nodes():
variables[f'x{i}'] = symbols(f'x{i}')
# ハミルトニアンを構築
H = 0
for (var1, var2), coeff in qubo_dict.items():
if var1 == var2:
H += coeff * variables[var1]
else:
H += coeff * variables[var1] * variables[var2]
# QUBOにコンパイル
qubo, qubo_offset = Compile(H).get_qubo()
# GPU/CPUに応じてサンプラーを選択
if self.use_gpu:
solver = sampler.ArminSampler(seed=self.seed) # GPU版
else:
solver = sampler.SASampler(seed=self.seed) # CPU版
# サンプリング実行
results = solver.run(qubo, shots=num_reads)
# 最良解を抽出
best_solution = None
best_energy = float('inf')
for result in results:
solution_dict = result[0]
energy = result[1]
if energy < best_energy:
best_energy = energy
best_solution = solution_dict
return best_solution, best_energy
ランダムグラフの生成
テスト用のランダムグラフを生成する関数
def generate_maxcut_graph(n_nodes: int, edge_probability: float = 0.5,
seed: int = None) -> nx.Graph:
"""
Erdős-Rényiモデルでランダムグラフを生成
"""
if seed is not None:
np.random.seed(seed)
G = nx.erdos_renyi_graph(n_nodes, edge_probability, seed=seed)
# グラフが連結でない場合は連結にする
if not nx.is_connected(G):
components = list(nx.connected_components(G))
for i in range(len(components) - 1):
node1 = list(components[i])[0]
node2 = list(components[i + 1])[0]
G.add_edge(node1, node2)
return G
解の評価
得られた解がどれだけのエッジをカットしているか評価する。
※本実装では変数は {0,1} と仮定している
def evaluate_maxcut_solution(graph: nx.Graph, solution: Dict[str, int]) -> int:
"""
MAX-CUT解の品質を評価（カットされたエッジ数を返す）
"""
cut_edges = 0
for i, j in graph.edges():
val_i = solution.get(f'x{i}', 0)
val_j = solution.get(f'x{j}', 0)
# 異なるパーティションにあればカット
if val_i != val_j:
cut_edges += 1
return cut_edges
性能比較実験
実験設定
以下の条件でGPUとCPUの性能を比較した。
- グラフサイズ: 5, 8, 10, 12, 15, 18, 20, 25, 30, 40, 50, 60, 70, 80, 90, 100ノード
- サンプル数: 500回/問題
- 各サイズでの試行回数: 2回
- GPU: GeForce RTX 2080
- CPU: Intel Core i7-9700K
実験コード
def run_scaling_test(max_nodes=100, runs_per_size=2):
node_sizes = [5, 8, 10, 12, 15, 18, 20, 25, 30, 40, 50, 60, 70, 80, 90, 100]
node_sizes = [n for n in node_sizes if n <= max_nodes]
comparator = TytanPerformanceComparator(seed=42)
# スケーリングテスト実行
df = comparator.run_scaling_test(
node_sizes=node_sizes,
edge_probability=0.5,
num_reads=500,
runs_per_size=runs_per_size
)
return df
# 実行
df = run_scaling_test(max_nodes=100, runs_per_size=2)
実験結果
以下は64件のテストを実施した結果である。
平均実行時間
| ソルバー | 平均実行時間 | 標準偏差 |
|---|---|---|
| GPU (ArminSampler) | 0.78 秒 | 0.13 秒 |
| CPU (SASampler) | 4.00 秒 | 4.86 秒 |
速度向上率
GPU版はCPU版に比べて平均5.14倍高速であった。
解の品質
両方のソルバー（GPU / CPU）で、全64件のテストケースで完全に同一の解を確認できた。
| グラフ規模 | 平均カット数 (GPU) | 平均カット数 (CPU) |
|---|---|---|
| 小規模（5-18ノード） | 23.5 | 23.5 |
| 中規模（20-50ノード） | 185.3 | 185.3 |
| 大規模（70-100ノード） | 1420.8 | 1420.8 |
※ノード数ごとの比較については後述のグラフを参照
本実験条件においては、GPU実装とCPU実装の間で最終的に得られる解の品質に有意な差は見られなかった。
グラフサイズ別の性能
小規模グラフ（5–18ノード）から大規模グラフ（100ノード）までを対象に、CPU実装とGPU実装の性能比較を行った。
| グラフ規模 | GPU 実行時間 | CPU 実行時間 | 速度向上率 |
|---|---|---|---|
| 小規模（5–18ノード） | 約0.7秒 | 約0.4–0.8秒 | 0.8–1.1倍（ほぼ同等） |
| 中規模（20–50ノード） | 約0.7–0.8 秒 | 約0.9–3.8 秒 | 約1.3–4.8 倍 |
| 大規模（70–100ノード） | 約0.9–1.1 秒 | 約7.2–17.1 秒 | 約8–16 倍 |
グラフサイズが小さいうちはGPUとCPUでほぼ同等の実行時間であったが、これは小規模問題ではGPU実装における初期化およびデータ転送の負荷が要因と思われる。
大きくなるほどGPUの優位性が顕著になる傾向が見られた。
可視化
結果をグラフ化することで、ノード数ごとの処理時間やカット数を視覚化した。
- Total Time： 合計処理時間の比較
- Best Cut Value： 最大カット数の比較
- Speedup： GPUの高速化率
Best Cut Valueのグラフを見るとCPUとGPUの結果が重なっており、同じ精度の結果になっていることが分かる。
その他の処理速度に関するグラフからは、ノード数18あたりまではCPUとGPUがほぼ同等だが、問題規模が大きくなるにつれてGPUの優位性が増していくことが確認できる。
まとめ
本記事では、MAX-CUT問題をGPU疑似量子アニーリングで解き、CPU実装との性能比較を行った。
その結果、解の品質はGPU・CPUともに同等である一方、実行時間についてはGPU版が平均して約5.14倍高速であることを確認した。
特にグラフサイズが大きくなるほどGPUの優位性が顕著になり、疑似量子アニーリングにおいてもGPUによる並列計算が有効に機能することが分かった。
今回はいずれも疑似量子アニーリング同士の比較であったが、今後は古典的な最適化アルゴリズムとの比較も行い、量子アルゴリズムの優位性について検証していきたい。