QAOAで最大カット問題を解く｜組合せ最適化をQiskitで

VQEと並ぶNISQ期の主役が QAOA（Quantum Approximate Optimization Algorithm）。組合せ最適化を量子×古典で近似的に解きます。この記事では定番の「最大カット問題」をQiskitで解き、最適な2分割を見つけます。

最大カット問題とは

グラフの頂点を2グループに分けたとき、「グループをまたぐ辺（カット）」が最大になる分け方を探す問題です。配置・分割・クラスタリングなど応用が広い、NP困難の代表例です。

準備

pip install qiskit qiskit-aer numpy

① グラフとカット値

4頂点の輪（正方形）を例にします。最適解は交互に塗る 1010 / 0101（カット=4）。

import numpy as np
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

edges = [(0, 1), (1, 2), (2, 3), (3, 0)]

def cut_value(bits):
    return sum(1 for i, j in edges if bits[i] != bits[j])

② QAOA回路（p=1）

コスト層は各辺に Rzz、ミキサー層は各ビットに Rx。

def qaoa_circuit(gamma, beta):
    qc = QuantumCircuit(4, 4)
    qc.h(range(4))                       # 一様な重ね合わせから開始
    for i, j in edges:
        qc.rzz(2 * gamma, i, j)          # コスト層：辺を位相に埋め込む
    for q in range(4):
        qc.rx(2 * beta, q)               # ミキサー層：探索を混ぜる
    qc.measure(range(4), range(4))
    return qc

def avg_cut(gamma, beta, shots=1000):
    counts = AerSimulator().run(qaoa_circuit(gamma, beta), shots=shots).result().get_counts()
    total = 0
    for b, c in counts.items():
        bits = [int(x) for x in b[::-1]]   # Qiskitは右端がqubit0
        total += cut_value(bits) * c
    return total / shots

③ 最適なパラメータを探す

γ・βの2次元をグリッド探索して、平均カットが最大になる角度を見つけます。

best = (-1, 0, 0)
for g in np.linspace(0, np.pi, 20):
    for be in np.linspace(0, np.pi / 2, 20):
        v = avg_cut(g, be, 500)
        if v > best[0]:
            best = (v, g, be)
print("最良の平均カット:", round(best[0], 2))

# 最良パラメータで多めにサンプリング
counts = AerSimulator().run(qaoa_circuit(best[1], best[2]), shots=3000).result().get_counts()
top = sorted(counts.items(), key=lambda x: -x[1])[:2]
for b, c in top:
    bits = [int(x) for x in b[::-1]]
    print(b, "カット=", cut_value(bits), "回数=", c)

出力はおおよそ:

最良の平均カット: 3.06
1010 カット= 4 回数= 841
0101 カット= 4 回数= 808

最頻の答えが 1010 と 0101＝カット4の最適解。QAOAが最大カットを見つけました。

まとめ

• QAOAはコスト層（Rzz）＋ミキサー層（Rx）を繰り返す変分アルゴリズム
• 最大カット問題を解いて 1010/0101（カット4）の最適解を発見
• p を増やすほど精度が上がるが最適化は難化
• NISQ期に現実的だが、古典に必ず勝つわけではない

もう少し詳しく（背景と理論）

QAOA は Farhi, Goldstone, Gutmann (2014) が提案した組合せ最適化の変分アルゴリズムで¹、コスト・ハミルトニアン（問題）とミキサー・ハミルトニアン（探索）を交互に p 回作用させます。p→∞ の極限では断熱量子計算に一致し最適解に収束しますが、実機では p は小さく抑えざるを得ません²。p=1 でも MaxCut に近似保証（一定比率以上のカット）が示されていますが³、古典の Goemans–Williamson 近似（0.878）を一般に上回るかは未解決で、「量子優位」は限定的です。パラメータ最適化のコスト、バレンプラトー、ノイズも実用の壁で、現状は研究段階と位置づけられます⁴。

次の一歩 🌸

もう一つの変分アルゴリズムVQE入門、勾配計算はパラメータシフト則、専用機の量子アニーリングへどうぞ。

Footnotes

1. Farhi, E., Goldstone, J., Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm." arXiv:1411.4028. ↩

2. QAOA は断熱定理（Adiabatic Theorem）に基づく断熱量子計算の Trotter 化とみなせる。層数 p を増やすほど断熱極限＝厳密最適に近づく。 ↩

3. p=1 の QAOA は3-正則グラフの MaxCut で近似比 0.6924 以上を保証する（Farhi et al.）。ただし古典の Goemans–Williamson (1995) は 0.878 を保証しており、量子が一般に勝つとは示されていない。 ↩

4. 小規模問題では古典の厳密解法・高性能ヒューリスティックに及ばないことが多い。QAOA の価値検証は活発な研究テーマ。 ↩