量子ゲートブログ1: QiskitのQAOAでMax-Cut Problemを解く！ – クオンタムファブリック株式会社

今回はQiskitのQAOAを使って、数式以外丸投げの形でMax-Cut Problemを解いてみました。

Max-Cut問題とは？

Max-Cut問題とは、グラフ（点と線でできた図）のノード（点）を「グループ0」と「グループ1」の2つに分けるとき、「違うグループ同士を結んでいるエッジ（線）」の数を最大化する問題です。

例えば、仲の悪い人たちを2つの部屋に分けるとき、できるだけ「敵対関係にあるペア」が別々の部屋になるように分ける、といったイメージです。

数式の考え方（QUBO）

量子コンピュータに解かせるために、以下の数式を使います。ノード iとjが繋がっているとき：

量子アニーリングでは(q1 – q2)^2と書きました。

量子ゲートで違うのは(QiskitのQudraticProgramを使う場合)、これを展開します。すると、q1^2 – 2(q1q2)+q2^2となりますね。

しかし、QUBOは0か1のため、二乗は意味がありません。より、q1 – 2(q1q2)+q2となります。

同じ組（0と0、または1と1）のとき：計算結果は 0
違う組（0と1、または1と0）のとき：計算結果は 1（ポイント獲得！）

この式をすべてのエッジで足し合わせ、その合計を最大化すれば正解が見つかります。

QAOAとは

QAOAはQuantum Approximate Optimization Algorithmという量子ゲートの王道のアルゴリズムです。組合せ最適化問題を解くのに適しています。しかし、中身は謎が多く、エンジニアレベルが終われば本格的に中身を調べていく予定です。

ステップ1：環境構築（インストール）

Google Colabなどの環境で、以下のコマンドを実行して必要なライブラリをインストールしてください。Qiskitの最新バージョン（1.0以降）に対応させています。

!pip install qiskit qiskit-optimization qiskit-algorithms

ステップ2：実装コード

このコードは、4つのノードが四角形（□）に繋がっているグラフを対象に、QAOA（量子近似最適化アルゴリズム）を使って解くものです。

# 1. 必要なライブラリのインポート
from qiskit_optimization import QuadraticProgram
from qiskit_algorithms import QAOA
from qiskit_algorithms.optimizers import COBYLA
from qiskit.primitives import StatevectorSampler as Sampler  # Qiskit 1.0+ 対応
from qiskit_optimization.algorithms import MinimumEigenOptimizer

# 2. グラフの定義
# (ノードi, ノードj) のペア。今回は 0-1, 1-2, 2-3, 3-0 が繋がっている四角形。
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]

# 3. 問題（QUBO）の定式化
qp = QuadraticProgram(name="Max_Cut_Level_1")

# 変数 x0, x1, x2, x3 をバイナリ（0か1）として定義
for i in range(4):
    qp.binary_var(name=f"x{i}")

linear_terms = {}     # 1次の項 (xi + xj)
quadratic_terms = {}  # 2次の項 (-2 * xi * xj)

# エッジごとに数式を組み立てる
for i, j in edges:
    # 1次の項：各ノードの係数に +1 を足していく
    linear_terms[f"x{i}"] = linear_terms.get(f"x{i}", 0) + 1
    linear_terms[f"x{j}"] = linear_terms.get(f"x{j}", 0) + 1
    
    # 2次の項：x_i * x_j の係数を -2 に設定
    quadratic_terms[(f"x{i}", f"x{j}")] = -2

# 目的関数を最大化（maximize）にセット
qp.maximize(linear=linear_terms, quadratic=quadratic_terms)

print("--- 定式化された問題 ---")
print(qp.prettyprint())
print("-" * 30)

# 4. QAOAの実行
sampler = Sampler() # 疑似量子コンピュータ（サンプラー）の準備
optimizer = COBYLA(maxiter=100) # 古典最適化アルゴリズム
qaoa = QAOA(sampler=sampler, optimizer=optimizer, reps=2) # QAOAの設定

# Qiskitの自動ソルバーにQAOAを渡して実行
optimizer_wrapper = MinimumEigenOptimizer(qaoa)
result = optimizer_wrapper.solve(qp)

# 5. 結果の表示
print("最適解のグループ分け:", result.x)
print("カットされたエッジの数（最大値）:", result.fval)

コードのポイント解説

StatevectorSampler: Qiskit 1.0から導入された新しいサンプラーです。エラーを避けるために as Sampler で読み込んでいます。
linear_terms.get(..., 0) + 1: 1つのノードが複数のエッジと繋がっている場合、係数を上書きせずに「足し合わせる」必要があります。これにより、グラフ全体の構造を正しく数式化できます。
MinimumEigenOptimizer: これが「レベル1」のキモです。これを使うことで、私たちが作ったQUBOの式を、量子コンピュータが理解できる「イジングモデル（ハミルトニアン）」へ自動で翻訳してくれます。

実行結果の目安

四角形のグラフの場合、隣同士が違う色（0と1）になるように、[0. 1. 0. 1.] または [1. 0. 1. 0.] と出力されれば大成功です！すべてのエッジ（4本）がカットされていることがわかります。

各関係に重さ(ウェイト)がある場合

係数がかかる場合はそれぞれの項に係数をかければいいため、以下の部分のコードだけ変わります。

for i, j, weight in edges:
    linear_terms[f"x{i}"] = linear_terms.get(f"x{i}", 0) + weight
    linear_terms[f"x{j}"] = linear_terms.get(f"x{j}", 0) + weight
    quadratic_terms[(f"x{i}", f"x{j}")] = -2*weight

まとめ

レベル1では、「解きたい問題を数式にする」ことだけに集中すれば、あとの難しい量子計算はQiskitがやってくれます。量子アニーリングに慣れている人なら、同じ感覚でゲート型量子コンピュータを操れるのがこの手法の強みです。

次は、重み付きのグラフや、さらに深い「レベル2」の自作ハミルトニアンにも挑戦してみましょう！