はじめに

前回、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による並列計算が有効に機能することが分かった。

今回はいずれも疑似量子アニーリング同士の比較であったが、今後は古典的な最適化アルゴリズムとの比較も行い、量子アルゴリズムの優位性について検証していきたい。